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つのクエリを続けます。

これを解決するには、次の手順に従います-

• 2つのマップmを作成し、カウントします

• イニシャライザで、次のタスクを実行します

• リード：=-1

• 0から回の配列のサイズまでの範囲のiの場合

  • x：=times [i]

  • count[persons[i]]の値を1増やします

  • count [lead] <=count [persons [i]]の場合、lead：=people[i]およびm[x]：=leadそれ以外の場合はm[x]：=Lead

• q（）メソッドは次のようになります

  • mのtの上限を減らし、対応する値を返します

理解を深めるために、次の実装を見てみましょう-

例

#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()
method like below:
q(3)
q(12)
q(25)
q(15)
q(24)
q(8)

出力

0
1
1
0
0
1