爱丽丝(Alice)正在玩街机游戏,想爬到排行榜的顶部,并想跟踪自己的排名。其排行榜的工作方式如下:
-得分最高的玩家在排行榜上排名排名。
具有相同分数的玩家将获得相同的排名号码,而接下来的玩家将获得紧随其后的排名号码。
例如,排行榜上的四个玩家得分分别为100、90、90和80。这些玩家的排名分别为1、2、2和3。如果爱丽丝的得分分别为70、80和105,则每场比赛后她的排名分别为第四,第三和第一。
#include <bits/stdc++.h>
using namespace std;
struct table{
int rank;
int score;
};
这是用于搜索分数的改进的二进制搜索功能。
int search(vector<table> v,int low,int high,int n,int x){
if(low<=high){
int mid =(high+low)/2;
if((v[mid].score==x) || (mid==0 && v[mid].score<x))
return v[mid].rank;
if(mid==n-1 && v[mid].score>x)
return (v[mid].rank + 1);
if(v[mid].score>x && x>v[mid+1].score && mid<n-1)
return v[mid+1].rank;
if(v[mid].score>x)
return search(v,mid+1,high,n,x);
else
return search(v,low,mid-1,n,x);
}
return -1;
}
主登山排行榜功能
vector<int> climbingLeaderboard(vector<int> scores, vector<int> alice) {
vector<table> v;
vector<int> res;
int n = scores.size();
int m = alice.size();
int x=1;
for(int i=0 ; i<n ; i++){
if(scores[i]!=scores[i-1] && i>0)
x++;
v[i].rank = x;
v[i].score = scores[i];
}
int z;
for(int i=0 ; i<m ; i++){
x=alice[i];
z = search(v,0,n-1,n,x);
res.push_back(z);
}
return res;
}
驱动程序]
int main(){ int scores_count; cin >> scores_count; vector<int> scores; `//vector for storing leaderboard scores` int k; for(int i=0 ; i<scores_count ; i++){ cin >> k; scores.push_back(k); } int game_count; `//number of games played by alice` vector<int> Alice; `//vector for storing Alice's scores` for(int i=0 ; i<game_count ; i++){ cin >> k; alice.push_back(k); } vector<int> result; `//vector for storing result rank of each game of Alice` result = climbingLeaderboard(scores,alice); for(auto i = result.begin() ; i!=result.end() ; i++){ cout << *i << endl; } return 0; }
爱丽丝(Alice)正在玩街机游戏,想爬到排行榜的顶部,并想跟踪自己的排名。其排行榜的工作方式如下:-得分最高的玩家排名...
问题:在您的climbingLeaderboard