Minimum Inversion Number
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Appoint description:
System Crawler (2015-03-30)
System Crawler (2015-03-30)
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
10
1 3 6 9 0 8 5 7 4 2
1 3 6 9 0 8 5 7 4 2
Sample Output
16
解题思路：1.求初始序列的逆序数 2.根据初始序列逆序数，递推出下一个序列的逆序数
1.当遍历到当前序列元素时，查询从该元素到n-1这段区间内的逆序和，即求大于该元素的元素已经出现几个（跟逆序的求法相逆，但是结果相同）。然后更新该结点及其父亲结点。遍历到结束，可求出该序列的逆序。
2.由于是从0开始连续的数求逆序，所以，有性质即从序列头部拿走a，相当于原序列的逆序减少a；放在尾部，相当于序列的逆序增加n-1-a；于是可以递推求出题目要求的所有序列的逆序。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
const int maxn=5500;
int num[maxn*4];
void PushUP(int rt){ num[rt]=num[rt*2]+num[rt*2+1];
}
void build(int rt,int L,int R){ num[rt]=0;
if(L==R)
return ;
build(lson);
build(rson);
}
int query(int rt,int L,int R,int l_ran,int r_ran){ if(l_ran<=L&&R<=r_ran){ return num[rt];
}
int ret=0;
if(l_ran<=mid){ ret+=query(lson,l_ran,r_ran);
}
if(r_ran>mid){ ret+=query(rson,l_ran,r_ran);
}
return ret;
}
void update(int rt,int L,int R,int pos){ if(L==R){ num[rt]++;
return ;
}
if(pos<=mid){ update(lson,pos);
}
if(pos>mid){ update(rson,pos);
}
PushUP(rt);
}
int main(){ int n;
while(scanf("%d",&n)!=EOF){ build(1,0,n-1);
int sum=0;
int a[5050];
for(int i=0;i<n;i++){ scanf("%d",&a[i]);
int tmp=query(1,0,n-1,a[i],n-1);
sum+=tmp;
update(1,0,n-1,a[i]);
}
int ans=sum;
for(int i=0;i<n;i++){ sum=sum+n-2*a[i]-1;
if(ans>sum){
ans=sum;
}
}
printf("%d\n",ans);
}
return 0;
}