মান লেযিয়ে একটি নির্বাচনে, i-তম ভোট persons[i]-কে times[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) - প্রতিটি q() কলের ফলাফল [0, 1, 1, 0, 0, 1]। কারণ সময় ৩-এ ভোট [0], ০ 앞서। সময় ১২-এ ভোট [0,1,1], ১ 앞서। সময় ২৫-এ ভোট [0,1,1,0,0,1], ১ 앞서 (টাই হলে সাম্প্রতিক ভোট জিতবে)।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
দুটি ম্যাপ m এবং count তৈরি করুন
ইনিশিয়ালাইজারে - lead := -1
i = 0 থেকে times.size()-1 পর্যন্ত লুপ চালান
x := times[i]
count[persons[i]]++ করুন
যদি count[lead] <= count[persons[i]] হয়, lead := persons[i] এবং m[x] := lead, অন্যথায় m[x] := lead
q() মেথড - m-এ t-এর upper_bound ডিক্রিমেন্ট করুন এবং সংশ্লিষ্ট ভ্যালু রিটার্ন করুন
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#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
