d794 - 世界排名
題目描述
題目要求，給定一串不重複的成績，每次輸入一個新的成績，輸出該成績目前的名次。
解題思路
這題的核心是需要高效地查詢一個數在排序後數列中的位置，並計算其排名。由於成績範圍很大 (0 到 2^64 - 1)，直接使用數組儲存並排序不可行。因此，我們需要使用離散化 (Discretization) 將成績映射到一個較小的範圍內。
具體步驟如下：
- 離散化： 將輸入的成績儲存到一個數組
b中，然後對b進行排序。使用lower_bound找到每個輸入成績a[i]在排序後的b數組中的位置，這個位置加 1 就是該成績的排名。 - Binary Indexed Tree (BIT)： 使用 BIT 結構來高效地計算排名。BIT 能夠在 O(log n) 的時間內查詢前綴和，也就是小於等於某個值的元素的個數。
- 更新 BIT： 每次查詢完一個成績的排名後，需要更新 BIT，表示已經出現了一個新的成績。
複雜度分析
- 時間複雜度: O(n log n)
- 排序
b數組需要 O(n log n) 的時間。 - 對於每個輸入成績，使用
lower_bound查找位置需要 O(log n) 的時間，查詢和更新 BIT 也需要 O(log n) 的時間。 - 總時間複雜度為 O(n log n) + n * O(log n) = O(n log n)。
- 排序
- 空間複雜度: O(n)
- 需要儲存輸入成績
a和b數組，以及 BIT 數組，空間複雜度為 O(n)。
- 需要儲存輸入成績
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n,BIT[100001],MAX_N=100001;
long long int a[100001],b[100001];
int lowerbit(int x){
return (x)&(-x);
}
int sum(int x){
int rt=0;
for(int i=x;i<=MAX_N;i+=lowerbit(i))
rt+=BIT[i];
return rt;
}
int edit(int x){
for(int i=x;i>0;i-=lowerbit(i))
++BIT[i];
}
int getID(long long int x){
return (lower_bound(b,b+n,x)-b)+1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
for(int i=0;i<=100000;++i){
BIT[i]=0;
}
for(int i=0;i<n;++i){
cin >> a[i];
b[i]=a[i];
}
sort(b,b+n);
for(int i=0;i<n;++i){
int tmp=getID(a[i]);
//cout << tmp << " ";
cout << sum(tmp)+1 << "\n";
edit(tmp);
}
}
}