可以交換相鄰的數,問最少交換幾次後數列變成非降的.. 對於每個數若小於左邊的數與左邊的數交換..大於右邊的數與右邊的數交換...如此可以推出所求的答案等價為這個數列的逆序數... 如果暴力查找逆序數是O(n^2)的...對於此題數據.不可接受... 采用分治的思想...在歸並排序的過程中邊排序邊統計逆序數的個數... Program:
#include<iostream> #include<stdio.h> #include<string.h> #include<set> #include<ctime> #include<algorithm> #include<queue> #include<cmath> #include<map> #define oo 100000007 #define ll long long #define pi acos(-1.0) #define MAXN 500005 using namespace std; int n,a[MAXN],temp[MAXN]; ll ans; void merge(int s1,int e1,int s2,int e2) { int x,i,j,num=0; i=s1,j=s2; for (x=s1;x<=e2;x++) { if (i>e1) temp[x]=a[j++]; else if (j>e2) temp[x]=a[i++]; else if (a[i]>a[j]) { temp[x]=a[j++]; ans+=e1-s1+1-num; //從後面段插進來的數插在了多少個前面段數的前面... }else temp[x]=a[i++],num++; } for (i=s1;i<=e2;i++) a[i]=temp[i]; return; } void merge_sort(int l,int r) { if (l==r) return; int mid=(l+r)/2; merge_sort(l,mid); merge_sort(mid+1,r); merge(l,mid,mid+1,r); return; } int main() { int i; while (~scanf("%d",&n)) { if (!n) break; for (i=1;i<=n;i++) scanf("%d",&a[i]); ans=0; merge_sort(1,n); printf("%I64d\n",ans); } return 0; }