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]이 됩니다. 큐(). 이는 시간 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]]이면 리드 :=people[i] 및 m[x] :=리드, 그렇지 않으면 m[x] :=리드
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)

출력