g735 - 110北二6.成績排名
題目描述
題目給定一個包含 n 個學生成績的列表，要求計算每個學生的排名。如果有多個學生成績相同，則他們應具有相同的排名，並且後續學生的排名應緊接在相同排名的學生之後。
解題思路
首先，使用 pair 儲存學生的成績和原始索引。然後，使用 sort 函數按照成績對學生進行排序。排序後，從高到低遍歷排序後的學生列表。如果當前學生的成績與下一個學生的成績相同，則將當前學生的排名設為下一個學生的排名。否則，將當前學生的排名設為 n - i，其中 i 是當前學生的索引。最後，輸出每個學生的排名。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n,ans[105];
pair <int,int> a[105];
int main(){
cin >> n;
for(int i=0;i<n;++i){
cin >> a[i].first;
a[i].second=i;
}
sort(a,a+n);
for(int i=n-1;i>=0;--i){
if(a[i].first==a[i+1].first){
ans[a[i].second]=ans[a[i+1].second];
}
else{
ans[a[i].second]=n-i;
}
}
for(int i=0;i<n;++i){
cout << ans[i] << " ";
}
}