Bầu cử trực tuyến trong C ++

Giả sử trong một cuộc bầu cử, lá phiếu thứ i được bỏ cho những người [i] tại thời điểm [i]. Bây giờ, chúng ta phải triển khai hàm truy vấn sau:TopVotedCandidate.q (int t), hàm này sẽ tìm số người dẫn đầu cuộc bầu cử tại thời điểm t. Phiếu bầu tại thời điểm t sẽ được tính vào truy vấn của chúng tôi. Nếu hòa, phiếu bầu gần đây nhất (trong số các ứng cử viên hòa) sẽ thắng.

Vì vậy, nếu chúng ta khởi tạo điều này bằng TopVotedCandidate ([0,1,1,0,0,1,0], [0,5,10,15,20,25,30]), sau đó gọi q () như:q ( 3), q (12), q (25), q (15), q (24), q (8), thì kết quả sẽ là [0, 1, 1, 0, 0, 1] cho mỗi lệnh gọi của q (). Điều này là do tại thời điểm 3, số phiếu bầu là [0] và 0 đang dẫn đầu. Tại thời điểm 12, số phiếu là [0,1,1], và ở đây 1 đang dẫn đầu. Tại thời điểm 25, số phiếu bầu là [0,1,1,0,0,1] và 1 đang dẫn đầu (khi các mối quan hệ đi đến phiếu bầu gần đây nhất.). Điều này tiếp tục cho 3 truy vấn nữa tại thời điểm 15, 24 và cuối cùng là 8.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo hai bản đồ m và đếm

• Trong trình khởi tạo, hãy thực hiện các tác vụ sau

• chì:=-1

• cho tôi trong phạm vi từ 0 đến kích thước của mảng thời gian

  • x:=lần [i]

  • tăng giá trị của số [người [i]] lên 1

  • nếu đếm [khách hàng tiềm năng] <=số lượng [người [i]] thì khách hàng tiềm năng:=người [i] và m [x]:=khách hàng tiềm năng nếu không thì m [x]:=khách hàng tiềm năng

• phương thức q () sẽ giống như

  • giảm giới hạn trên của t theo m và trả về giá trị tương ứng

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class TopVotedCandidate {
   public:
   map <int, int> m;
   map <int, int> count;
   TopVotedCandidate(vector<int>& persons, vector<int>& times) {
      int lead = -1;
      for(int i = 0; i < times.size(); i++){
         int x = times[i];
         count[persons[i]]++;
         if(count[lead] <= count[persons[i]]){
            lead = persons[i];
            m[x] = lead;
         }else{
            m[x] = lead;
         }
      }
   }
   int q(int t) {
      return ((--m.upper_bound(t)) -> second);
   }
};
main(){
   vector<int> v1 = {0,1,1,0,0,1,0}, v2 = {0,5,10,15,20,25,30};
   TopVotedCandidate ob(v1, v2);
   cout << (ob.q(3)) << endl;
   cout << (ob.q(12)) << endl;
   cout << (ob.q(25)) << endl;
   cout << (ob.q(15)) << endl;
   cout << (ob.q(24)) << endl;
   cout << (ob.q(8)) << endl;
}

Đầu vào

Initialize the class using [0,1,1,0,0,1,0] and [0,5,10,15,20,25,30]. Call q()
method like below:
q(3)
q(12)
q(25)
q(15)
q(24)
q(8)

Đầu ra

0
1
1
0
0
1