ออกแบบลีดเดอร์บอร์ดใน C++

สมมติว่าเราต้องออกแบบคลาสลีดเดอร์บอร์ด มีสามฟังก์ชันที่แตกต่างกัน –

• addScore(playerId, score) - สิ่งนี้จะอัปเดตกระดานผู้นำโดยเพิ่มคะแนนให้กับคะแนนของผู้เล่นที่กำหนด เมื่อไม่มีผู้เล่นดังกล่าวที่มี id ที่ระบุในกระดานผู้นำ ให้เพิ่มเขาในกระดานผู้นำด้วยคะแนนที่กำหนด
• top(K) - จะคืนค่าผลรวมคะแนนของผู้เล่น K อันดับต้นๆ
• reset(playerId) − สิ่งนี้จะรีเซ็ตคะแนนของผู้เล่นด้วย id ที่ระบุเป็น 0 รับประกันได้ว่าผู้เล่นถูกเพิ่มในกระดานผู้นำก่อนที่จะเรียกใช้ฟังก์ชันนี้

เริ่มแรก กระดานผู้นำควรว่างเปล่า

หากเราดำเนินการดังต่อไปนี้ −

• ลีดเดอร์บอร์ดลีดเดอร์บอร์ด =ลีดเดอร์บอร์ดใหม่ ();
• ลีดเดอร์บอร์ด.addScore(1,73); // ลีดเดอร์บอร์ดคือ [[1,73]];
• ลีดเดอร์บอร์ด.addScore(2,56); // ลีดเดอร์บอร์ดคือ [[1,73],[2,56]];
• ลีดเดอร์บอร์ด.addScore(3,39); // ลีดเดอร์บอร์ดคือ [[1,73],[2,56],[3,39]];
• ลีดเดอร์บอร์ด.addScore(4,51); // ลีดเดอร์บอร์ดคือ [[1,73],[2,56],[3,39],[4,51]];
• ลีดเดอร์บอร์ด.addScore(5,4); // ลีดเดอร์บอร์ดคือ [[1,73],[2,56],[3,39],[4,51],[5,4]];
• ลีดเดอร์บอร์ด.top(1); // คืนค่า 73;
• ลีดเดอร์บอร์ด.รีเซ็ต(1); // ลีดเดอร์บอร์ดคือ [[2,56],[3,39],[4,51],[5,4]];
• ลีดเดอร์บอร์ด.รีเซ็ต(2); // ลีดเดอร์บอร์ดคือ [[3,39],[4,51],[5,4]];
• ลีดเดอร์บอร์ด.addScore(2,51); // ลีดเดอร์บอร์ดคือ [[2,51],[3,39],[4,51],[5,4]];
• ลีดเดอร์บอร์ด.top(3); // คืนค่า 141 =51 + 51 + 39;

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดลำดับความสำคัญของคิวของคู่จำนวนเต็มที่เรียกว่า pq สร้างหนึ่งแมปของคีย์ประเภท int และค่าประเภท int m สำหรับการเริ่มต้น มันจะล้างแผนที่ และถ้าคิวไม่ว่าง ให้ลบองค์ประกอบทั้งหมดออกจากคิว
• เมธอด addScore() จะเป็น −
  • ถ้ามี playerId แสดงว่า m[playerId] :=m[playerId] + score
  • แทรกคู่ (m[playerId], playerId) ลงใน pq
  • มิฉะนั้น m[playerId] =คะแนน
• เมธอด top() จะเป็นแบบนี้
• สร้างเวกเตอร์ของคู่ temp, set sum :=0
• ในขณะที่ k ไม่ใช่ 0
  • curr :=ด้านบนของ pq ลบออกจาก pq
  • ถ้า m[ค่าที่สองของคู่สกุลเงิน] =ค่าแรกของคู่สกุลเงิน
    • ลด k ขึ้น 1
    • sum :=sum + ค่าแรกของสกุลเงิน
    • ใส่เคอร์เซอร์ลงในอุณหภูมิ
• สำหรับ i ในช่วง 0 ถึงขนาดของอุณหภูมิ
  • ใส่ 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