सी++ में ऑनलाइन चुनाव

मान लीजिए एक चुनाव में, i-th वोट व्यक्तियों के लिए डाला गया था [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 से समय के आकार की सीमा में

  • x :=बार[i]

  • गिनती [व्यक्तियों [i]] के मान को 1 से बढ़ाएं

  • अगर गिनती [लीड] <=गिनती [व्यक्तियों [i]], तो लीड:=व्यक्ति [i] और एम [एक्स]:=लीड अन्यथा एम [एक्स]:=लीड

• q() विधि इस तरह होगी

  • t की ऊपरी सीमा को m में घटाएं, और संबंधित मान लौटाएं

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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