Thiết kế bảng xếp hạng trong C++

Thiết kế lớp Leaderboard với 3 hàm:

• addScore(playerId, score): cộng điểm cho người chơi, thêm mới nếu chưa có.
• top(K): trả về tổng điểm top K người chơi.
• reset(playerId): đặt điểm người chơi về 0.

Ví dụ: thêm điểm cho 5 người, top(1)=73, reset 1,2, thêm lại 2 với 51, top(3)=141.

Giải thuật (Heap ưu tiên + Map)

1. Map m lưu điểm hiện tại, priority queue pq lưu (điểm, id) max-heap.
2. addScore: cập nhật m, push (m[id], id) vào pq.
3. top(K): pop từ pq cho đến khi lấy đủ K phần tử khớp m (lazy deletion), tính tổng, push lại các phần tử đã pop.
4. reset: đặt m[id] = 0.

Ví dụ 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(auto &p : temp) pq.push(p);
        return sum;
    }
    void reset(int playerId) { m[playerId] = 0; }
};

int 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; // 73
    ob.reset(1); ob.reset(2);
    ob.addScore(2,51);
    cout << ob.top(3) << endl; // 141
    return 0;
}

Đầu vào

Khởi tạo leaderboard, dùng các hàm như main()

Đầu ra

73 102