看了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; }
