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.
InputThe 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.
OutputFor each case, output the minimum inversion number on a single line.
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
题意：给定n个数的整数序列，每次可将序列首个数放到最后一位，其余数相对位置不变，通过这样的操作可以得到n种序列，要求这n种序列中倒置数的最小个数，即满足下标i<j,a[i]>a[j]。
其实说白了就是求不停倒置的最小逆序数
求逆序数用线段树或者树状数组都是挺方便的，每次加一个数进去，看此时后面的数有几个。
但这样肯定会超时，我们可以首先写出一开始的逆序数，发现每次倒置后，逆序数为减少a[i],而增加n-1-a[i]的。减少比它小的，增加比它大的
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int a[maxn<<];
int add[maxn];
#define lson l,m,k<<1
#define rson m+1,r,k<<1|1
void hehe(int k)
{
a[k]=a[k<<]+a[k<<|];
}
void build(int l,int r,int k)
{
a[k]=;//先是假设这棵树都为0
if(l==r) return ;
int m=(l+r)>>;
build(lson);
build(rson);
}
int query(int x,int y,int l,int r,int k)
{
if(x<=l&&r<=y)
return a[k]; int m=(l+r)>>;
int s=;
if(x<=m) s+=query(x,y,lson);
if(y>m) s+=query(x,y,rson);
return s;
}
void update(int p,int l,int r,int k)
{
if(l==r)
{
a[k]++;//增加个数
return;
}
int m=(l+r)>>;
if(p<=m) update(p,lson);
else update(p,rson);
hehe(k);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
build(,n-,);
int sum=;//为一开始的逆序数
for(int i=;i<n;i++)
{
scanf("%d",&add[i]);
sum+=query(add[i],n-,,n-,);
update(add[i],,n-,);
}
int minn=sum;
for(int i=;i<n;i++)
{
sum+=n-add[i]-add[i]-;
minn=min(minn,sum);
}
cout<<minn<<endl;
}
return ;
}