Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence Input
Output
Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
大意：求冒泡排序交换的个数，也就是求逆序数，套一下模板
#include<cstring> #include<cstdio> #include<algorithm> const int MAX = 510000; int a[MAX],temp[MAX]; int ans = 0; void mergesort(int *a,int first,int mid,int last,int *temp) { int i = first,j = mid + 1; int k = first; while( i <= mid && j <= last){ if(a[i] <= a[j]) temp[k++] = a[i++]; else { ans += j - k; temp[k++] = a[j++]; } } while( i <= mid) temp[k++] = a[i++]; while( j <= last) temp[k++] = a[j++]; for(int i = first;i <= last;i++) a[i] = temp[i]; } void mergearray(int *a,int first,int last,int *temp) { if(first < last){ int mid = (first + last) >> 1; mergearray(a,first,mid,temp); mergearray(a,mid+1,last,temp); mergesort(a,first,mid,last,temp); } } int main() { int n; scanf("%d",&n); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); mergearray(a,1,n,temp); printf("%d",ans); return 0; }
原文：http://www.cnblogs.com/zero-begin/p/4369654.html