C ++在线选举

假设在一次选举中，第i次投票是在时间[i]上对人[i]进行的。现在，我们必须实现以下查询功能：TopVotedCandidate.q（int t），它将找到在时间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