Online Election ใน C++

คำอธิบายปัญหา

มีการโหวต persons[i] ที่เวลา times[i] ต้องการตอบคำถาม: ที่เวลา t ใครนำหน้าสุด (ถ้าเท่ากัน คนที่โหวตล่าสุดนำ)

ตัวอย่าง: persons=[0,1,1,0,0,1,0], times=[0,5,10,15,20,25,30], query q(3)=0, q(12)=1, q(25)=1, q(15)=0, q(24)=0, q(8)=1

วิธีแก้ปัญหา (Precompute + Binary Search)

1. ประมวลผลโหวตตามลำดับเวลา เก็บ leader ณ แต่ละเวลาใน map
2. ใช้ map เก็บ {time: leader}
3. query(t): หาเวลาที่ <= t มากที่สุด (upper_bound แล้วลด 1)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class TopVotedCandidate {
public:
    map<int, int> leaderAtTime;
    map<int, int> voteCount;
    
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        int lead = -1;
        for(int i = 0; i < times.size(); i++) {
            int p = persons[i];
            int t = times[i];
            voteCount[p]++;
            if(voteCount[p] >= voteCount[lead]) {
                lead = p;
            }
            leaderAtTime[t] = lead;
        }
    }
    
    int q(int t) {
        auto it = leaderAtTime.upper_bound(t);
        if(it == leaderAtTime.begin()) return -1;
        it--;
        return it->second;
    }
};

int main() {
    vector<int> persons = {0,1,1,0,0,1,0};
    vector<int> times = {0,5,10,15,20,25,30};
    TopVotedCandidate ob(persons, times);
    cout << ob.q(3) << " " << ob.q(12) << " " << ob.q(25) << " "
         << ob.q(15) << " " << ob.q(24) << " " << ob.q(8);
    return 0;
}

อินพุต

Initialize with [0,1,1,0,0,1,0] and [0,5,10,15,20,25,30]. Queries: q(3) q(12) q(25) q(15) q(24) q(8)

เอาต์พุต

0 1 1 0 0 1