মনে করুন আমাদের একটি Leaderboard ক্লাস ডিজাইন করতে হবে, তিনটি ভিন্ন ফাংশন আছে -
- `addScore(playerId, score)` - এটি দিয়ে দেয়া `playerId`-র স্কোরে `score` যোগ করে লিডারবোর্ড আপডেট করবে। যদি দিয়ে দেয়া আইডিয়ের প্লেয়ার লিডারবোর্ডে না থাকে, তবে তাকে দিয়ে দেয়া স্কোরসহ লিডারবোর্ডে যোগ করবে।
- `top(K)` - এটি টপ K প্লেয়ারের স্কোর সমষ্টি রিটার্ন করবে।
- `reset(playerId)` - এটি দিয়ে দেয়া আইডির প্লেয়ারের স্কোর ০ করবে। এটি গ্যারান্টিড যে প্লেয়ারটি এই ফাংশন কল করার আগে লিডারবোর্ডে যোগ করা হয়েছিল।
প্রাথমিকভাবে লিডারবোর্ড খালি থাকবে।
যদি আমরা নিচের অপারেশনগুলো পারফর্ম করি -
- Leaderboard leaderboard = new Leaderboard ();
- leaderboard.addScore(1,73); // leaderboard is [[1,73]];
- leaderboard.addScore(2,56); // leaderboard is [[1,73],[2,56]];
- leaderboard.addScore(3,39); // leaderboard is [[1,73],[2,56],[3,39]];
- leaderboard.addScore(4,51); // leaderboard is [[1,73],[2,56],[3,39],[4,51]];
- leaderboard.addScore(5,4); // leaderboard is [[1,73],[2,56],[3,39],[4,51],[5,4]];
- leaderboard.top(1); // returns 73;
- leaderboard.reset(1); // leaderboard is [[2,56],[3,39],[4,51],[5,4]];
- leaderboard.reset(2); // leaderboard is [[3,39],[4,51],[5,4]];
- leaderboard.addScore(2,51); // leaderboard is [[2,51],[3,39],[4,51],[5,4]];
- leaderboard.top(3); // returns 141 = 51 + 51 + 39;
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- একটি প্রায়োরিটি কিউ `pq` (ইন্টিজার পেয়ার), এবং একটি ম্যাপ `m` (ইন্ট কি এবং ইন্ট ভ্যালু) সংজ্ঞায়িত করুন। ইনিশিয়ালাইজেশনে, ম্যাপ ক্লিয়ার করুন, এবং যদি কিউ খালি না থাকে, তবে সব এলিমেন্ট ডিলিট করুন।
- `addScore()` মেথড নিচের মোতাবিক হবে -
- যদি `playerId` বিদ্যমান থাকে, তবে `m[playerId] := m[playerId] + score`
- `(m[playerId], playerId)` পেয়ারটি `pq`-তে ইনসার্ট করুন
- অন্যথায় `m[playerId] = score`
- `top()` মেথড নিচের মোতাবিক হবে -
- `temp` নামক একটি পেয়ার ভেক্টর, `sum := 0` সেট করুন
- যখন `k` ০ না হয়
- `curr := pq`-এর টপ, `pq`-থেকে ডিলিট করুন
- যদি `m[curr.second] == curr.first`
- `k`-কে ১ কমান
- `sum := sum + curr.first`
- `curr`-কে `temp`-এ ইনসার্ট করুন
- `i` = 0 থেকে `temp`-এর আকার পর্যন্ত
- `temp[i]`-কে `pq`-তে ইনসার্ট করুন
- `reset()` ফাংশন নিচের মোতাবিক হবে -
- `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
