題意：輸入一個整數n（n <= 5000），然後輸入0至n-1的一個序列a[1]，a[2]，...，a[n]，把a[1]放到a[n]後面，又成一個序列，再把a[2]放到a[1]後面，又成一個序列……求這幾個序列的最小逆序對數。 ——>>寒假訓練賽第一場的C題，今天用樹狀數組過了。 只要求出第一個序列的逆序對數就好辦了。這裡，個人用BIT來求。 1 3 6 9 0 8 5 7 4 2 （因為樹狀樹組的結點從1開始，於是加個1，映射一下） 2 4 7 10 1 9 6 8 5 3，這時，從右往左，用cnt計數逆序對數，訪問3，前3項和為0（這裡不是a的前3項和），把3這個位置標記，加到BIT裡去，接著訪問5，前5項和為1，因為剛才3的位置標了一個1，cnt += sum[5]就有了1，把5這個位置標記，加到BIT裡去，接著訪問8，前8項和為2，因為3和5的位置標了一個1……這就求出了逆序對數。 www.2cto.com 接著求其他n-1個序列的逆序對數，0至n-1組成的序列，太好了！為什麼這樣說？如果第1個數為k，那麼其右邊就有k個數比它小（分別是k-1, k-2, ..., 1, 0），如果最後一個數是k，那麼其左邊就有n-k-1個數比它大（分別是k+1, k+2, ..., n-1)。所以，剛才求出了第一個序列的最小逆序對數後，依次把第1個數放到最後，並統計該序列的逆序對數cnt - a[i] + (n-a[i]-1)，更新最小值就是。 [cpp] #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 5000 + 10; int a[maxn], C[maxn], lowerbit[maxn], n; int sum(int x) //BIT求前x項和 { int ret = 0; while(x > 0) { ret += C[x]; x -= lowerbit[x]; } return ret; } void add(int x, int d) //BIT修改 { while(x <= n) { C[x] += d; x += lowerbit[x]; } } int main() { int i; for(i = 1; i <= maxn; i++) lowerbit[i] = i&(-i); //打表 while(~scanf("%d", &n)) { getchar(); for(i = 1; i <= n; i++) scanf("%d", &a[i]); memset(C, 0, sizeof(C)); int cnt = 0; for(i = n; i >= 1; i--) //從後往前 { cnt += sum(a[i]+1); add(a[i]+1, 1); } int MIN = cnt; for(i = 1; i <= n; i++) MIN = min(MIN, cnt = cnt - a[i] + (n-a[i]-1)); printf("%d\n", MIN); } return 0; }
