|
|
題目鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1484
  /**//*
 題意：
給出0 ~ N-1 (1 <= N <= 5000) 的一個(gè)排列, 經(jīng)過循環(huán)移位，一共有N個(gè)排列，
問這N個(gè)排列中逆序?qū)?shù)目最小的。
解法：
樹狀數(shù)組
思路：
樹狀數(shù)組求逆序數(shù)有一個(gè)經(jīng)典算法，把數(shù)字大小對(duì)應(yīng)到樹狀數(shù)組的小標(biāo)，然后
從后往前遍歷每個(gè)數(shù)字，統(tǒng)計(jì)比這個(gè)數(shù)字小的數(shù)的個(gè)數(shù)，然后將這個(gè)數(shù)插入到樹狀
數(shù)組中，遍歷完畢，累加和就是該序列的逆序?qū)Φ臄?shù)目。
這題要求序列循環(huán)移位n次，每次移位統(tǒng)計(jì)一次逆序?qū)Γ詈蟮玫阶钚〉模绻?br>按照前面的算法，最好的情況是O(n^2log(n))，所以需要找到一些技巧，將復(fù)雜度
降下來，我們發(fā)現(xiàn)以下兩個(gè)數(shù)列：
1. a1, a2,  , an-1, an
2. a2, a3, , an, a1
第二個(gè)是第一個(gè)循環(huán)左移一位的結(jié)果，如果將第一個(gè)序列的逆序數(shù)分情況討論就是
S = A + B；其中A = (a2~an)本身的逆序?qū)?shù)目；B = a1和(a2~an)的逆序?qū)?shù)目；
而第二個(gè)序列中則是S' = A + B'；其中B' = (n-1) - B，于是S和A如果已知，那么
就可以輕松求得S' = A + (n-1) - (S - A)。這樣一來，只要知道前一個(gè)序列的逆
序數(shù)，下一個(gè)序列就可以在O(1)的時(shí)間內(nèi)求得。只要每次更新S 和 A 的值即可。
更加一般化的，S表示當(dāng)前序列的逆序數(shù)對(duì)數(shù)，A表示比當(dāng)前數(shù)小的數(shù)的個(gè)數(shù)，
題目中數(shù)列是一個(gè)排列，所以A的值其實(shí)就是當(dāng)前值減一。
 */
#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;
}
|