一直没理解题目什么意思,后来看网上的解释才明白。
1,暴力解法
给你一个有0-n-1组成的序列。这个序列有n-1中排列方式(题中所给的),让你求出那种排列的逆序数最小。
n-1中排列中,每次都把最前面的a[i]放在序列最后面。此时关键就来了,当a[i]在最前面时,后面一定有a[i]个比他小的数,n-a[i]-1个比a[i]大的数,所以每次把a【i】移到最后时,逆序数就会变化,a[i]到最后时,对应a[i]的逆序数为n-a[i]-1-a[i].
所以先求出原来序列的总逆序数sum,然后遍历,每次都更新总序列的逆序数,即sum= sum + n- a [ i ] -1 -a [ i ].
#include"stdio.h" #include"string.h" #define N 5004 int main() { int n; int ans; int min; int a[N]; int i,j; while(scanf("%d",&n)!=-1) { for(i=0;i<n;i++) scanf("%d",&a[i]); ans=0; for(i=0;i<n;i++) { for(j=i+1;j<n;j++) if(a[i]>a[j])ans++; } min=ans; for(i=0;i<n-1;i++) { ans=ans-a[i]+(n-a[i]-1); if(min>ans) min=ans; } printf("%d\n",min); } return 0; }
2,线段树。
因为线段树直接就是有序的查找数据,所以要求a[i]对应的逆序数,只需要find(a【i】+1,n,1)就可以了。
主一要处理0的情况。。
#include"stdio.h" #include"string.h" #define N 5004 struct node { int x,y,mid,sum; }A[N*3]; void build(int x,int y,int t) { A[t].x=x; A[t].y=y; A[t].mid=(x+y)/2; A[t].sum=0; if(x==y)return ; build(x,A[t].mid,t*2); build(A[t].mid+1,y,2*t+1); return ; } void insert(int x,int t) { if(A[t].x==A[t].y&&A[t].x==x) { A[t].sum=1; return ; } if(x<=A[t].mid) insert(x,2*t); else insert(x,2*t+1); A[t].sum=A[2*t].sum+A[2*t+1].sum; return ; } int find(int x,int y,int t) { int sum; sum=0; if(A[t].x==x&&A[t].y==y) return A[t].sum; if(y<=A[t].mid) sum+=find(x,y,2*t); else if(x>A[t].mid) sum+=find(x,y,2*t+1); else { sum+=find(x,A[t].mid,2*t); sum+=find(A[t].mid+1,y,2*t+1); } return sum; } int main() { int a[N]; int i,n; while(scanf("%d",&n)!=-1) { build(1,n,1); int sum=0; for(i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]++;//避免0的出现 if(a[i]+1<=n) sum+=find(a[i]+1,n,1); insert(a[i],1); } int ans=99999999; for(i=1;i<=n;i++) { sum=sum+n-(a[i]-1)-1-(a[i]-1); if(ans>sum)ans=sum; } printf("%d\n",ans); } return 0; }