Problem Description
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
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.
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
101 3 6 9 0 8 5 7 4 2
Sample Output
16
Solution：
题意就是给定$n$个数的序列（$0$到$n-1$），求出序列的符合要求的排列中逆序对的个数最小值，（符合要求就是可以每次将序列第一位数移到序列最后一位或者不移）。
思路就是先用树状数组求出原序列的逆序对个数$tot$，设首位数为$x$，则每次移动逆序对增加的个数为$x$后面比$x$大的数的个数（即$n-x$），每次减小的个数为$x$后面比$x$小的数的个数（即$x-1$）。
那么移动前逆序对个数为$tot$，移动首位后逆序数$tot=tot-(x-1)+(n-x)$，于是枚举$n$次移动的情况（第$1$次表示不移，即原序列），更新最小值$ans$就行了。
（坑点在于$HDU$上数据有多组，开始我还以为自己错了、查了半天～～手动滑稽～～）
代码：
#include#include#include#define il inline#define ll long long#��ǿ,��ǿdefine N 5005using namespace std;int n,a[N],c[N],ans=520520520,tot;il int gi(){ int a=0;char x=getchar();bool f=0; while((x<'0'||x>'9')&&x!='-')x=getchar(); if(x=='-')x=getchar(),f=1; while(x>='0'&&x<='9')a=a*10+x-48,x=getchar(); return f?-a:a;}il void update(int x,int k){ while(x<=n){ c[x]+=k; x+=x&-x; }}il int sum(int x){ int ans=0; while(x){ ans+=c[x]; x-=x&-x; } return ans;}int main(){ while(scanf("%d",&n)==1){ memset(c,0,sizeof(c)); ans=520520520,tot=0; for(int i=1;i<=n;i++)a[i]=gi()+1; for(int i=n;i>=1;i--){ update(a[i],1); tot+=sum(a[i]-1); } for(int i=1;i<=n;i++)tot=tot-(a[i]-1)+(n-a[i]),ans=min(ans,tot); printf("%d\n",ans); } return 0;}