C++ में ऑनलाइन इलेक्शन (Online Election)

मान लीजिए एक चुनाव में, i-वां वोट persons[i] को समय times[i] पर डाला गया था। अब, हमें निम्न क्वेरी फंक्शन लागू करना है: TopVotedCandidate.q(int t) यह समय t पर चुनाव का नेतृत्व करने वाले व्यक्ति की संख्या खोजेगा। समय t पर डाले गए वोट हमारी क्वेरी में गिने जाएंगे। यदि टाई है, तो सबसे हालिया वोट (टाई किए गए उम्मीदवारों में से) जीतता है।

समाधान दृष्टिकोण

1. दो मैप्स m और count बनाएं

2. इनिशियलाइज़र में: लीडर ट्रैक करें, प्रत्येक समय पर लीडर को m में स्टोर करें

3. q() में: t का अपर बाउंड घटाकर संबंधित मान लौटाएं

C++ कार्यान्वयन

#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); 
    } 
}; 

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; 
    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; 
    return 0; 
}

इनपुट

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

आउटपुट

0 1 1 0 0 1