d788 - 排名順序
題目描述
題目要求在每次加入新的分數後，立即輸出該分數的排名。輸入包含多組測試案例，每組案例首先給定一個整數 N，表示接下來會有 N 個分數。然後，逐行讀取 N 個不同的分數，並在讀取每個分數後輸出其排名。排名定義為比該分數小的分數個數加 1。
解題思路
這題可以使用二元索引樹 (Binary Indexed Tree, BIT) 來高效地計算排名。BIT 是一種資料結構，可以有效地計算前綴和，並支援快速更新。
解題步驟如下：
- 初始化 BIT 陣列為 0。
- 對於每個輸入的分數 t：
- 使用 BIT 查詢小於等於 t 的分數個數，即
sum(t)。 - 輸出
sum(t) + 1，即 t 的排名。 - 更新 BIT，將 t 的出現次數加 1，即
edit(t)。
- 使用 BIT 查詢小於等於 t 的分數個數，即
lowerbit(x) 函數用於計算 x 的最低有效位。sum(x) 函數用於計算 BIT 陣列中從 1 到 x 的前綴和。edit(x) 函數用於更新 BIT 陣列，將 x 的值加 1。
複雜度分析
- 時間複雜度: O(N log N)
- 空間複雜度: O(N)
程式碼
#include <iostream>
using namespace std;
int MAX_N=100005,BIT[100005];
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 main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,t;
while(cin >> n){
for(int i=0;i<MAX_N;++i){
BIT[i]=0;
}
for(int i=0;i<n;++i){
cin >> t;
cout << sum(t)+1 << "\n";
edit(t);
}
}
}