ধরুন আমাদের একটি লিডারবোর্ড ক্লাস ডিজাইন করতে হবে, তিনটি ভিন্ন ফাংশন আছে −
- addScore(playerId, স্কোর) - এটি প্রদত্ত প্লেয়ারের স্কোরে স্কোর যোগ করে লিডারবোর্ড আপডেট করবে। লিডারবোর্ডে প্রদত্ত আইডি সহ এমন কোন খেলোয়াড় না থাকলে, তাকে প্রদত্ত স্কোর সহ লিডারবোর্ডে যোগ করুন।
- টপ(K) − এটি সেরা K খেলোয়াড়দের স্কোর যোগফল ফিরিয়ে দেবে।
- reset(playerId) − এটি প্রদত্ত আইডি সহ প্লেয়ারের স্কোর 0 এ রিসেট করবে। এটা নিশ্চিত যে এই ফাংশনটি কল করার আগে প্লেয়ারকে লিডারবোর্ডে যোগ করা হয়েছিল।
প্রাথমিকভাবে, লিডারবোর্ডটি খালি হওয়া উচিত।
যদি আমরা নিচের মত ক্রিয়া সম্পাদন করি -
- লিডারবোর্ড লিডারবোর্ড =নতুন লিডারবোর্ড ();
- leaderboard.addScore(1,73); // লিডারবোর্ড হল [[1,73]];
- leaderboard.addScore(2,56); // লিডারবোর্ড হল [[1,73],[2,56]];
- leaderboard.addScore(3,39); // লিডারবোর্ড হল [[1,73],[2,56],[3,39]];
- leaderboard.addScore(4,51); // লিডারবোর্ড হল [[1,73],[2,56],[3,39],[4,51]];
- leaderboard.addScore(5,4); // লিডারবোর্ড হল [[1,73],[2,56],[3,39],[4,51],[5,4]];
- leaderboard.top(1); // ফেরত 73;
- leaderboard.reset(1); // লিডারবোর্ড হল [[2,56],[3,39],[4,51],[5,4]];
- leaderboard.reset(2); // লিডারবোর্ড হল [[3,39],[4,51],[5,4]];
- leaderboard.addScore(2,51); // লিডারবোর্ড হল [[2,51],[3,39],[4,51],[5,4]];
- leaderboard.top(3); // ফেরত দেয় 141 =51 + 51 + 39;
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- pq নামক পূর্ণসংখ্যা জোড়ার একটি অগ্রাধিকার সারি সংজ্ঞায়িত করুন, int টাইপ কী এবং int টাইপ মান m এর একটি মানচিত্র তৈরি করুন। প্রারম্ভিকতার জন্য, এটি মানচিত্রটি সাফ করবে, এবং যদি সারি খালি না থাকে, তাহলে সারি থেকে সমস্ত উপাদান মুছুন৷
- addScore() পদ্ধতি −
- এর মত হবে
- যদি playerId থাকে, তাহলে m[playerId] :=m[playerId] + স্কোর
- pq এ একটি জোড়া (m[playerId], playerId) সন্নিবেশ করান
- অন্যথায় m[playerId] =স্কোর
- টপ() পদ্ধতিটি এরকম হবে
- জোড়ার তাপমাত্রার একটি ভেক্টর তৈরি করুন, যোগফল সেট করুন :=0
- যদিও k 0
- নয়
- curr :=pq এর শীর্ষ, pq থেকে মুছুন
- যদি m[curr pair এর দ্বিতীয় মান] =curr pair এর প্রথম মান
- k কে 1 দ্বারা কমিয়ে দিন
- সমষ্টি :=যোগফল + curr এর প্রথম মান
- টেম্পে curr ঢোকান
- আমি 0 থেকে টেম্পের মাপের মধ্যে
- pq-এ temp[i] ঢোকান
- রিসেট() ফাংশন −
- এর মত হবে
- m[playerId] =0
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Leaderboard {
public:
priority_queue< pair <int,int> > pq;
map < int, int > m;
Leaderboard() {
m.clear();
while(!pq.empty())pq.pop();
}
void addScore(int playerId, int score) {
if(m.find(playerId)!=m.end()){
m[playerId] += score;
}
else m[playerId] = score;;
pq.push({m[playerId], playerId});
}
int top(int k) {
vector < pair <int,int> > temp;
int sum = 0;
while(k){
pair <int, int> curr = pq.top();
pq.pop();
if(m[curr.second] == curr.first){
k--;
sum += curr.first;
temp.push_back(curr);
}
}
for(int i = 0; i < temp.size(); i++)pq.push(temp[i]);
return sum;
}
void reset(int playerId) {
m[playerId] = 0;
}
};
main(){
Leaderboard ob;
ob.addScore(1,73);
ob.addScore(2,56);
ob.addScore(3,39);
ob.addScore(4,51);
ob.addScore(5,4);
cout <<ob.top(1) << endl;
ob.reset(1);
ob.reset(2);
ob.addScore(2,51);
cout <<ob.top(2) << endl;
} ইনপুট
Initialize leader board then use the functions to see different results. See the main() functionদেখুন
আউটপুট
73 102
