Trong bầu cử, phiếu i cho persons[i] lúc times[i]. Triển khai TopVotedCandidate.q(t): tìm người dẫn đầu lúc t (phiếu lúc t tính vào). Nếu hòa, người vote gần nhất thắng.
Ví dụ: persons=[0,1,1,0,0,1,0], times=[0,5,10,15,20,25,30]. q(3)→0, q(12)→1, q(25)→1, q(15)→0, q(24)→0, q(8)→1.
Giải pháp:
Duyệt times, cập nhật count vote, leader hiện tại
Lưu m[timestamp] = leader vào map
q(t): upper_bound(t) trong map, giảm iterator, trả về leader
Ví dụ
#include <bits/stdc++.h> using namespace std; class TopVotedCandidate { public: map <int, int> m, 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; } }; int 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<<ob.q(12)<<endl<<ob.q(25)<<endl<<ob.q(15)<<endl<<ob.q(24)<<endl<<ob.q(8)<<endl; }Đầu vào
Khởi tạo [0,1,1,0,0,1,0] [0,5,10,15,20,25,30]. Gọi q(3) q(12) q(25) q(15) q(24) q(8)
Đầu ra
0 1 1 0 0 1