思路:我们可以先确定第一个数字串的逆序数,之后每一次将首个数字移到数字串的尾部都有一个规律,那就是逆序数减去a[i],再加上(n-a[i]-1),a[i]代表第i个数字。所以我们可以先建一个空树,然后依照第一个数字串依次往线段树中填充数字,每填充一个数字都找出在它之前比它大的数字有多少个。最后求出第一个数字串的逆序数之后根据已经找出来的规律递推一下得到最小的逆序数。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int MAXN=5005; struct node { int l,r; int num;//本节点表示区间内数字的个数 }segTree[4*MAXN]; int a[MAXN]; void build(int root,int l,int r) { segTree[root].l=l; segTree[root].r=r; segTree[root].num=0; if(segTree[root].l==segTree[root].r) return; int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); } void update(int root,int x) { if(segTree[root].l==segTree[root].r) { if(segTree[root].l==x) segTree[root].num++; return; } int mid=(segTree[root].l+segTree[root].r)>>1; if(x<=mid) update(root<<1,x); else update(root<<1|1,x); //回溯更新 segTree[root].num=segTree[root<<1].num+segTree[root<<1|1].num; } int query(int root,int l,int r) { if(l>r)//因为数字的大小是0到n-1,可能会出现l>r的情况 return 0; if(segTree[root].l==l&&segTree[root].r==r) return segTree[root].num; int mid=(segTree[root].l+segTree[root].r)>>1; if(r<=mid) return query(root<<1,l,r); else if(l>mid) return query(root<<1|1,l,r); else return query(root<<1,l,mid)+query(root<<1|1,mid+1,r); } int main() { int n,i,sum,ans; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) scanf("%d",&a[i]); build(1,0,n-1); sum=0; for(i=0;i<n;i++) { //找出在这个数字之前比它大的有多少个,并且累加 sum+=query(1,a[i]+1,n-1); //更新节点 update(1,a[i]); } ans=sum; //找出最小的逆序数 for(i=0;i<n-1;i++) { sum=sum-a[i]+n-a[i]-1; if(sum<ans) ans=sum; } printf("%d\n",ans); } return 0; }