मान लीजिए हमें एक लीडरबोर्ड क्लास डिज़ाइन करनी है, इसमें तीन अलग-अलग फंक्शन्स हैं -
- addScore(playerId, score) - यह दिए गए प्लेयर के स्कोर में स्कोर जोड़कर लीडरबोर्ड को अपडेट करेगा। जब दिए गए आईडी वाला कोई प्लेयर लीडरबोर्ड में नहीं है, तो उसे दिए गए स्कोर के साथ लीडरबोर्ड में जोड़ें।
- top(K) - यह टॉप K प्लेयर्स के स्कोर का योग लौटाएगा।
- reset(playerId) - यह दिए गए आईडी वाले प्लेयर के स्कोर को 0 पर रीसेट करेगा। यह गारंटी है कि इस फंक्शन को कॉल करने से पहले प्लेयर को लीडरबोर्ड में जोड़ा गया था।
प्रारंभ में, लीडरबोर्ड खाली होना चाहिए।
यदि हम नीचे दिए गए ऑपरेशन करते हैं -
- Leaderboard leaderboard = new Leaderboard ();
- 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] + score
- पेयर (m[playerId], playerId) को pq में डालें
- अन्यथा m[playerId] = score
- top() मेथड इस प्रकार होगा
- पेयर्स का एक वेक्टर temp बनाएं, sum := 0 सेट करें
- जब तक k 0 नहीं है
- curr := pq का टॉप, pq से डिलीट करें
- यदि m[curr पेयर का सेकंड मान] = curr पेयर का फर्स्ट मान
- k को 1 से घटाएं
- sum := sum + curr का फर्स्ट मान
- 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; }इनपुट
लीडरबोर्ड इनिशियलाइज़ करें फिर अलग-अलग परिणाम देखने के लिए फंक्शन्स का उपयोग करें। main() फंक्शन देखें
आउटपुट
73 102
