Minimum Inversion Number

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12141Accepted Submission(s): 7413

题意是:

给N个数(0~N-1)组成的序列,求出它的逆序数(就是由多少对数,前一个比后一个大),

然后每次把第一个数放到最后,再求逆序数,然后输出所有逆序数中最小的那个...

思路:

第1步,向数组中依次存入初始序列,同时用线段树求出这个数贡献的的逆序数,就是查询比这个数大的数有几个,及用查询线段树 [x[i],N-1] 这个范围

具体方法是:叶子节点只存储两个值0和1,0表示该叶子节点表示的数还没有存入,1表示该叶子节点表示的数已经存入了,非叶子节点为两个子节点的和,表示该范围内有几个数已经存入了数组;数组中每存入一个数,先去查询比它大的数有几个,就是它贡献的逆序数,加入sum,然后更新该点,表示已经放入了;最终sum就是初始序列的逆序数

第2步,每次把第一个数放到最后,因为知道了前一个序列的逆序数,就可以用O(1)的方法求出它的逆序数

具体方法是:

比如初始序列是1 3 6 9 0 8 5 7 4 2,根据第1步,求出了它的逆序数sum

现在要把1移到最后,构成3 6 9 0 8 5 7 4 2 1,求该序列的逆序数

在初始序列中,1贡献的逆序数是 排在它后面的,所有比它小的数的个数(只有0,1个),由取走1,sum先减去1;放到最后,能增加的逆序数,要往前看,是所有比1大的数的个数,是N-1-1个,所以sum=(sum-1)+(N-1-1)

然后逸动3,sum先减去3(比3小的是0,1,2),移到最后,sum加上N-1-3

因为初始序列是存储在数组中的,所以用一个for循环,每次移动x[i],比它小的有x[i]个,比它大的有N-1-x[i]个,所以sum=(sum-x[i])+(N-1-x[i])

@H_403_141@#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <iostream> #include <algorithm> using namespace std; //#define lson left,mid,index<<1 //#define rson mid+1,right,index<<1|1 const int MAXN=5010; int num[MAXN<<2]; void PushUp(int ret) { num[ret]=num[ret<<1]+num[ret<<1|1]; } void BuildTree(int left,int right,int ret) { num[ret]=0; if(left==right) return ; int mid=(left+right)>>1; BuildTree(left,ret<<1); BuildTree(mid+1,ret<<1|1); } void Update(int target,int left,int ret) { if(left==right) { num[ret]++; return ; } int mid=(left+right)>>1; if(target<=mid) Update(target,left,ret<<1); else Update(target,mid+1,ret<<1|1); PushUp(ret); } /* int Query(int L,int R,int ret) { if(L<=left && right<=R) return num[index]; int mid=(left+right)>>1; int ans=0; if(L<=mid) ans+=Query(L,R,lson); if(R>mid) ans+=Query(L,rson); return ans; } */ int Query(int L,int ret) { if(L<=left && right<=R) return num[ret]; int mid=(left+right)>>1; if(R<=mid) return Query(L,ret<<1); else if(mid<L) return Query(L,ret<<1|1); else return Query(L,ret<<1)+Query(L,ret<<1|1); } int main() { freopen("1394.in","r",stdin); // freopen("1394.out","w",stdout); int n; int a[5100]; while(scanf("%d",&n)!=EOF) { int sum=0; BuildTree(0,n-1,1); for(int i=0;i<n;i++) { scanf("%d",a+i); sum+=Query(a[i],1); Update(a[i],1); } int ans=sum; for(int i=0;i<n;i++) { sum+=n-a[i]-1-a[i]; ans=min(ans,sum); } printf("%d\n",ans); } return 0; }