hdu - 1394 - Minimum Inversion Number
题意：输入一个整数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.zzzyk.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;
}
补充：软件开发 , C++ ,
