Giả sử chúng ta phải thiết kế một lớp Bảng xếp hạng, có ba chức năng khác nhau -
- addScore (playerId, điểm số) - Điều này sẽ cập nhật bảng xếp hạng bằng cách thêm điểm số vào điểm số của người chơi nhất định. Khi không có người chơi nào có id đã cho trong bảng thành tích, hãy thêm anh ta vào bảng thành tích với số điểm đã cho.
- top (K) - Điều này sẽ trả về tổng điểm của K người chơi hàng đầu.
- đặt lại (playerId) - Thao tác này sẽ đặt lại điểm của người chơi có id đã cho thành 0. Người chơi được đảm bảo rằng đã được thêm vào bảng xếp hạng trước khi gọi hàm này.
Ban đầu, bảng thành tích sẽ trống.
Nếu chúng ta thực hiện các thao tác như bên dưới -
- Bảng dẫn đầu bảng xếp hạng =Bảng dẫn đầu mới ();
- leaderboard.addScore (1,73); // bảng thành tích là [[1,73]];
- leaderboard.addScore (2,56); // bảng thành tích là [[1,73], [2,56]];
- leaderboard.addScore (3,39); // bảng thành tích là [[1,73], [2,56], [3,39]];
- leaderboard.addScore (4,51); // bảng thành tích là [[1,73], [2,56], [3,39], [4,51]];
- leaderboard.addScore (5,4); // bảng thành tích là [[1,73], [2,56], [3,39], [4,51], [5,4]];
- leaderboard.top (1); // trả về 73;
- leaderboard.reset (1); // bảng thành tích là [[2,56], [3,39], [4,51], [5,4]];
- leaderboard.reset (2); // bảng thành tích là [[3,39], [4,51], [5,4]];
- leaderboard.addScore (2,51); // bảng thành tích là [[2,51], [3,39], [4,51], [5,4]];
- leaderboard.top (3); // trả về 141 =51 + 51 + 39;
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định hàng đợi ưu tiên của các cặp số nguyên được gọi là pq, tạo một bản đồ gồm các khóa kiểu int và các giá trị kiểu int m. Đối với quá trình khởi tạo, nó sẽ xóa bản đồ và nếu hàng đợi không trống, hãy xóa tất cả các phần tử khỏi hàng đợi.
- Phương thức addScore () sẽ giống như -
- nếu có playerId thì m [playerId]:=m [playerId] + điểm
- chèn một cặp (m [playerId], playerId) vào pq
- nếu không thì m [playerId] =điểm
- Phương thức top () sẽ giống như sau
- tạo một vectơ gồm các cặp tạm thời, đặt tổng:=0
- while k không phải 0
- curr:=đầu pq, xóa khỏi pq
- if m [giá trị thứ hai của cặp curr] =giá trị đầu tiên của cặp curr
- giảm k đi 1
- sum:=sum + giá trị đầu tiên của curr
- chèn cuộn tóc vào nhiệt độ
- cho tôi trong phạm vi từ 0 đến kích thước của nhiệt độ
- chèn temp [i] vào pq
- Hàm reset () sẽ có dạng -
- m [playerId] =0
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
Initialize leader board then use the functions to see different results. See the main() function
Đầu ra
73 102