मान लीजिए कि हमें एक लीडरबोर्ड वर्ग डिजाइन करना है, तीन अलग-अलग कार्य हैं -
- addScore(playerId, Score) - यह दिए गए खिलाड़ी के स्कोर में स्कोर जोड़कर लीडरबोर्ड को अपडेट करेगा। जब लीडरबोर्ड में दी गई आईडी वाला ऐसा कोई खिलाड़ी नहीं है, तो उसे दिए गए स्कोर के साथ लीडरबोर्ड में जोड़ें।
- top(K) - यह शीर्ष K खिलाड़ियों के स्कोर का योग लौटाएगा।
- reset(playerId) - यह दिए गए आईडी वाले खिलाड़ी के स्कोर को 0 पर रीसेट कर देगा। यह गारंटी है कि खिलाड़ी को इस फ़ंक्शन को कॉल करने से पहले लीडरबोर्ड में जोड़ा गया था।
प्रारंभ में, लीडरबोर्ड खाली होना चाहिए।
अगर हम नीचे की तरह ऑपरेशन करते हैं -
- लीडरबोर्ड लीडरबोर्ड =नया लीडरबोर्ड ();
- लीडरबोर्ड.एडस्कोर(1,73); // लीडरबोर्ड है [[1,73]];
- लीडरबोर्ड.एडस्कोर(2,56); // लीडरबोर्ड है [[1,73],[2,56]];
- लीडरबोर्ड.एडस्कोर(3,39); // लीडरबोर्ड है [[1,73],[2,56],[3,39]];
- लीडरबोर्ड.एडस्कोर(4,51); // लीडरबोर्ड है [[1,73],[2,56],[3,39],[4,51]];
- लीडरबोर्ड.एडस्कोर(5,4); // लीडरबोर्ड है [[1,73],[2,56],[3,39],[4,51],[5,4]];
- लीडरबोर्ड.टॉप(1); // 73 लौटाता है;
- लीडरबोर्ड.रीसेट(1); // लीडरबोर्ड है [[2,56],[3,39],[4,51],[5,4]];
- लीडरबोर्ड.रीसेट(2); // लीडरबोर्ड है [[3,39],[4,51],[5,4]];
- लीडरबोर्ड.एडस्कोर(2,51); // लीडरबोर्ड है [[2,51],[3,39],[4,51],[5,4]];
- लीडरबोर्ड.टॉप(3); // रिटर्न 141 =51 + 51 + 39;
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- pq नामक पूर्णांक जोड़े की प्राथमिकता कतार को परिभाषित करें, int प्रकार कुंजियों और int प्रकार मानों का एक नक्शा बनाएं। आरंभीकरण के लिए, यह मानचित्र को साफ़ कर देगा, और यदि कतार खाली नहीं है, तो कतार से सभी तत्वों को हटा दें।
- एडस्कोर () विधि इस तरह होगी −
- यदि खिलाड़ी आईडी मौजूद है, तो m[playerId] :=m[playerId] + स्कोर
- पीक्यू में एक जोड़ी (m[playerId], playerId) डालें
- अन्यथा m[playerId] =स्कोर
- शीर्ष () विधि इस तरह होगी
- जोड़े अस्थायी का एक वेक्टर बनाएं, योग सेट करें:=0
- जबकि k 0 नहीं है
- curr :=pq के ऊपर, pq से हटाएं
- अगर m[कर्र पेयर का दूसरा मान] =कर्व पेयर का पहला मान
- k को 1 से घटाएं
- योग :=योग + मुद्रा का प्रथम मान
- अस्थायी में करंट डालें
- मैं के लिए 0 से लेकर अस्थायी आकार के बीच
- अस्थायी[i] pq में डालें
- रीसेट () फ़ंक्शन इस तरह होगा -
- 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