C ++在线选举
假设在一次选举中，第i次投票是在时间[i]上对人[i]进行的。现在，我们必须实现以下查询功能：TopVotedCandidate.q（intt），它将找到在时间t领导选举的人数。在时间t进行的投票将计入我们的查询。如果出现平局，则以最近的投票（在并列的候选人中）获胜。
因此，如果我们使用TopVotedCandidate（[0,1,1,0,0,1,0]，[0,5,10,15,20,25,30]）初始化它，则调用q()：q(3)，q(12)，q(25)，q(15)，q(24)，q(8)，则每次调用的结果将为[0，1，1，0，0，1]q()。这是因为在时间3，票数是[0]，而0是领先。在时间12，票数为[0,1,1]，此处1为领先。在时间25，票数为[0,1,1,0,0,1]，而1是领先的（因为平局最近的票数）。在时间15、24和最后8，这将继续进行另外3个查询。
为了解决这个问题，我们将遵循以下步骤-
创建两个映射m并计数
在初始化程序中，执行以下任务
铅：=-1
对于范围为0到时间数组大小的i
x：=次[i]
将count[persons[i]]的值增加1
如果count[lead]<=count[persons[i]]，则lead：=person[i]和m[x]：=Lead否则，m[x]：=Lead
该q()方法将像
减小t在m中的上限，并返回相应的值
让我们看下面的实现以更好地理解-
示例
#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;
}输入值
Initialize the class using [0,1,1,0,0,1,0] and [0,5,10,15,20,25,30]. Call q()方法 like below: q(3) q(12) q(25) q(15) q(24) q(8)
输出结果
0 1 1 0 0 1