题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1394
题目大意：
给出一个序列，一对逆序数就是满足i<j&&a[i]>a[j]条件的一对数字。
每次将a数组的最后一个数放到数组的第一位上，原数组向后移动一位，得到一个新的序列，
求这些序列中最小的逆序数。（每个数都在0-n-1范围内）
求解思路：
（1）逆序数的性质：一个序列第i次循环的逆序数Pi=P(i-1)+（n-1-a[i]）-a[i]。
（2）可以通过暴力求解，每次找最小值就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = ;
const int INF = ;
int a[maxn];
int main(void)
{
int mi,cnt,i,j,num,n;
while(~scanf("%d",&n))
{
memset(a,,sizeof(a));
for(i=;i<n;i++) scanf("%d",&a[i]);
mi=INF;cnt=;
for(i=;i<n;i++)
for(j=i+;j<n;j++)
if(a[i]>a[j]) cnt++;
if(mi>cnt) mi=cnt;
for(i=;i<n;i++)
{
cnt=cnt+(n--a[i])-a[i];
if(mi>cnt) mi=cnt;
}
printf("%d\n",mi);
}
return ;
}
（3）线段树做法：
先初始化线段树都为0，然后输入每个数，每个数字+1，即改为1-n区间，判断b[i]+1到n区间内有无数字，有的话逆序数就+1
然后再更新节点b[i]表示这个节点被访问过了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = ;
const int INF = ;
int a[maxn<<],b[maxn];
void pushup(int x)
{
a[x]=a[x*]+a[x*+];
}
void build(int x,int l,int r)
{
if(l==r)
{
a[x]=;return ;
}
int mid=(l+r)/;
build(x*,l,mid);
build(x*+,mid+,r);
pushup(x);
}
void update(int x,int l,int r,int pos)
{
if(l==r)
{
a[x]++;return ;
}
int mid=(l+r)/;
if(pos<=mid) update(x*,l,mid,pos);
if(pos>mid) update(x*+,mid+,r,pos);
pushup(x);
}
int query(int x,int l,int r,int A,int B)
{
if(A<=l&&r<=B) return a[x];
int mid=(l+r)/,ans=;
if(A<=mid) ans+=query(x*,l,mid,A,B);
if(B>mid) ans+=query(x*+,mid+,r,A,B);
return ans;
}
int main(void)
{
int n,i,ans,mi;
while(~scanf("%d",&n))
{
memset(a,,sizeof(a));
memset(b,,sizeof(b));
build(,,n);
ans=;mi=INF;
for(i=;i<=n;i++)
{
scanf("%d",&b[i]);
b[i]++;
ans+=query(,,n,b[i]+,n);
update(,,n,b[i]);
}
if(mi>ans) mi=ans;
for(i=;i<n;i++)
{
ans=ans+(n-b[i]+)-b[i];
if(mi>ans) mi=ans;
}
printf("%d\n",mi);
}
return ;
}
（4）归并排序做法
归并排序时，当a[j]>a[i]时，每次记录tmp+=(mid-i+1),最终求出的tmp就是这个序列的逆序数。
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = ;
int a[maxn],b[maxn],temp[maxn],tmp;
void Merge_Sort(int l,int r,int mid)
{
int pos=,i=l,j=mid+;
while(i<=mid&&j<=r)
{
if(a[i]>a[j]) tmp+=(mid+-i),temp[pos++]=a[j++];
else temp[pos++]=a[i++];
}
while(i<=mid) temp[pos++]=a[i++];
while(j<=r) temp[pos++]=a[j++];
for(i=;i<pos;i++) a[i+l]=temp[i];
}
void Merge(int l,int r)
{
if(l==r) return ;
int mid=(l+r)/;
Merge(l,mid);
Merge(mid+,r);
Merge_Sort(l,r,mid);
}
int main(void)
{
int n,ans,i;
while(~scanf("%d",&n))
{
for(i=;i<n;i++)
{
scanf("%d",&a[i]);b[i]=a[i];
}
tmp=;ans=;
Merge(,n-);
ans=tmp;
for(i=;i<n;i++){
tmp=tmp+n--b[i]*;
if(ans>tmp) ans=tmp;
}
printf("%d\n",ans);
}
return ;
}