应该是一道树状数组和线段树的题目，但是，可能是因为数据过少，能够用类似暴力的方法PASS。但是方法中还是比暴力要有一点巧妙地办法；
Minimum Inversion Number
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 45 Accepted Submission(s) : 30
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
10 1 3 6 9 0 8 5 7 4 2
16
题目大意：让我们求一个序列的逆序数，什么是逆序数呢，就是下标i<j，但是ai>aj，这样就叫做逆序数，数列中的每个数字都有一个逆序数，可能是0。之后把这个序列里面的逆序数相加，得到一次结果。之后，每次都把开头的那一项移动到最后一项，然后重复上述的步骤算出和值，直到把原数列的最后一个数变到数列的前面来，然后比较每一次算的和值，输出最小的。
其实也就是让你找，每次移动数列的之后，每一个数之前有多少比他大的然后累加起来。
解题思路：
假设下面这组例子，
5 4 7 2
1、先对这个数组中的元素进行排序，存到一个新数组里面
2、用暴力的方式，先算出第一次的总和sum；
3、然后开始移动元素，一直5排序后排在第三位（查找元素位置的时候因为之前已经排好序，所以我用了二分查找），那么前面有2个比他小的，后面有一个比他大的。那么比他小的，
因为他移动到后面了，所以对应的逆序数的数值的和值应该减一，因为5移动到最后，前面一定有比他大的，那么有几个就加上几个，因为5对应的逆序数的数值也要及时更新，加进总的和值里面。
4.之后一次做第三步的工作就可以了，基本都是0（1）
代码如下：
//题目连接：http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1001&ojid=0&cid=2398&hide=0
//Minimum Inversion Number//
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 6000
int num[MAX];
int order[MAX];
int binsrch(int *r,int n,int k);
int main()
{
int i,j,k;
int n,sum;
int count;
int position;
int result[MAX];
int t;
while(scanf("%d",&n)!=EOF)
{
t=0;
count=sum=0;
for(i=1;i<=n;i++)
{
scanf("%d",&num[i]);
order[i]=num[i];
result[i]=0;
}
sort(order,order+n+1);
for(i=1;i<=n;i++)
{
for(j=1;j<=i-1;j++)
{
if(num[j]>num[i])
count++;
}
sum+=count;
count=0;
}
for(k=1;k<=n-1;k++)
{
position=binsrch(order,n,num[k]);
sum=sum-(position-1)+n-position;
result[t++]=sum;
}
sort(result,result+t-1);
printf("%d\n",result[0]);
}
return 0;
}
int binsrch(int *r,int n,int k)
{ int low,high,mid,found;
low=1;
high=n;
found=0;
while((low<=high)&&(found==0))
{ mid=(low+high)/2;
if(k>r[mid])
low=mid+1;
else
if(k==r[mid])
found=1;
else
high=mid-1;
}
if(found==1)
return(mid);
else
return(0);
}