HDU 1394 Minimum Inversion Number
看了Not Only Success 的分类和题解。。
首先求出原序列的逆序数,as,
然后假设当前队首元素为a,
那么a之后有a-1个比a小的元素,有n-a个比a大的元素,
当把a放在队尾时,比a小的元素的逆序数-1,即as-=a-1
而对于a来说,前面比a大的元素又各增加了1个逆序对,即as+=n-a,
于是枚举一次就可以找到最小的as了。
这里是线段树求逆序对算法:
build的过程相当于insert的过程,就是把值为x的元素插到线段树中,
然后求当前x+1,n的元素的个数y,就是新生成逆序对的个数,即as+=y。
[cpp]
#include<stdio.h>
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
#define X 5010
int a[X*4],b[X],ll,rr;
void pushup(int rt){
a[rt]=a[rt*2]+a[rt*2+1];
}
void build(int x,int l,int r,int rt){
if(l==r){a[rt]++;return ;}
int mid=l+r>>1;
if(x<=mid)build(x,lson);
else build(x,rson);
pushup(rt);
}
int que(int l,int r,int rt){
if(ll<=l&&rr>=r)return a[rt];
int as=0,mid=l+r>>1;
if(ll<=mid)as+=que(lson);
if(rr>mid) as+=que(rson);
return as;
}
int main(){
int i,n,x,as,tmp;
while(~scanf("%d",&n)){
for(i=1;i<=n*4;i++)a[i]=0;
tmp=0;as=n*n;
for(i=1;i<=n;i++)
scanf("%d",&b[i]),b[i]++;
for(i=1;i<=n;i++){
ll=b[i],rr=n;
tmp+=que(1,n,1);
build(b[i],1,n,1);
}
for(i=1;i<n;i++){
tmp+=n+1-2*b[i];
as=tmp<as?tmp:as;
}
printf("%d\n",as);
}
return 0;
}
补充:软件开发 , C++ ,