|
|
題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1484
  /**//*
 題意：
給出0 ~ N-1 (1 <= N <= 5000) 的一個排列, 經過循環移位，一共有N個排列，
問這N個排列中逆序對數目最小的。
解法：
樹狀數組
思路：
樹狀數組求逆序數有一個經典算法，把數字大小對應到樹狀數組的小標，然后
從后往前遍歷每個數字，統計比這個數字小的數的個數，然后將這個數插入到樹狀
數組中，遍歷完畢，累加和就是該序列的逆序對的數目。
這題要求序列循環移位n次，每次移位統計一次逆序對，最后得到最小的，如果
按照前面的算法，最好的情況是O(n^2log(n))，所以需要找到一些技巧，將復雜度
降下來，我們發現以下兩個數列：
1. a1, a2,  , an-1, an
2. a2, a3, , an, a1
第二個是第一個循環左移一位的結果，如果將第一個序列的逆序數分情況討論就是
S = A + B；其中A = (a2~an)本身的逆序對數目；B = a1和(a2~an)的逆序對數目；
而第二個序列中則是S' = A + B'；其中B' = (n-1) - B，于是S和A如果已知，那么
就可以輕松求得S' = A + (n-1) - (S - A)。這樣一來，只要知道前一個序列的逆
序數，下一個序列就可以在O(1)的時間內求得。只要每次更新S 和 A 的值即可。
更加一般化的，S表示當前序列的逆序數對數，A表示比當前數小的數的個數，
題目中數列是一個排列，所以A的值其實就是當前值減一。
 */
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 5001
int n;
short c[maxn], val[maxn];
int lowbit(int x) {
return x & (-x);
}
void add(int pos) {
  while(pos <= n) {
c[pos] ++;
pos += lowbit(pos);
 }
}
int sum(int pos) {
int s = 0;
while(pos > 0) {
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
int main() {
int i;
while(scanf("%d", &n) != EOF) {
for(i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
val[i] = x + 1;
}
for(i = 1; i <= n; i++)
c[i] = 0;
int ans = 0;
for(i = n; i >= 1; i--) {
int x = sum(val[i] - 1);
add(val[i]);
ans += x;
}
int Min = ans;
int A = val[1] - 1;
for(i = 2; i <= n; i++) {
ans = ans - A + (n-1-A);
A = val[i] - 1;
if(ans < Min)
Min = ans;
}
printf("%d\n", Min);
}
return 0;
}
|