题目大意为：一个从a1到给顶一个an的数组，如果存在两个数（ai，aj）如果满足i<j并且ai>aj，那么就称其为一个逆序数，可以一次把第一个数移到最后面，为一个新的序列，求给定一个序列，其所有情况的最小逆序数个数。
可以分别确定每一个序列的逆序数个数，一个序列的逆序数个数需要从每一个数都进行判断，判断当前的数（假设ai）后面的小于ai的数的个数，储存在ai中做参数，那么所有的a1到an的参数和即为该序列的逆序数个数。
可以假设有4个数：
3 2 1 4
首先代入4，S[4]==0,将0返回，并将C[4]记为1，代入1，S[1]==0,将0返回,C[1]记为1。代入2，前面的小于2的数只有1个，S[2]==1,将1返回，C[2]记为1。代入3，S[3]==2,将2返回，记C[3]为1。
可以总结：先将树状数组初始化为0，从右到左遍历，求得S[i]之和就是总的逆序数的和，遍历完以后自增1。
又是前n项求和的运算，便很自然地想到树状数组：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
#define MMAX 5005
int C[5005];
int sum(int i)
{
int ans=0;
while (i>0)
{
ans+=C[i];
i-=lowbit(i);
}
return ans;
}
void add(int i,int k)
{
while (i<=MMAX)
{
C[i]+=k;
i+=lowbit(i);
}
}
void main()
{
int a[MMAX]={0};
int i,j,k=0,n,m;
scanf("%d",&n);
m=n;
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
for (i=n;i>=1;i--)
{
k+=sum(a[i]);
add(a[i],1);
}
printf("%d\n",k);
}
这只是一个序列的求解逆序数，那么当该序列发生了改变之后呢？
我们可以依次移动一个数据来得到一系列的数字值，记下最下的值，该值就是最终所求的解。
假设移动一个值，a[i]，减去a[i]之后，ai后面有ai个比其小的数，ai放在最后其前面有n-1-ai个比其大的数，所以有k=k-a[i]+(n-1-a[i]);
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
#define MMAX 5010
int C[5010];
int sum(int i)
{
int ans=0;
while (i>0)
{
ans+=C[i];
i-=lowbit(i);
}
return ans;
}
void add(int i,int k)
{
while (i<=MMAX)
{
C[i]+=k;
i+=lowbit(i);
}
}
void main()
{
int a[MMAX]={0};
int i,j,k=0,n,m;
while (scanf("%d",&n)!=EOF&&n!=0)
{
memset(C, 0, sizeof(C));
memset(a,0,sizeof (a));
k=0;
m=n;
for (i=0;i<n;i++)
scanf("%d",&a[i]);
for (i=n-1;i>=0;i--)
{
k+=sum(a[i]+1);
add(a[i]+1,1);
}
int ans=k;
for(i=0;i<n;i++)
{
k+=n-(a[i]<<1)-1;
if(k<ans)ans=k;
}
printf("%d\n",ans);
}
}
