|
|
题目链接：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;
}
|