点我看题
题意:让相邻的两个数不断的交换,直到整个序列不下降,求最少交换次数.
分析:归并排序求逆序数.
参考代码:
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int maxn = 1e3+5; int n; int a[maxn]; int ans; int tmp[maxn]; void Merge( int l, int mid, int r) { int i = l; int j = mid+1; int k = l; while( i <= mid && j <= r) { if( a[i] > a[j]) { tmp[k++] = a[j++]; ans += mid-i+1; } else tmp[k++] = a[i++]; } while( i <= mid) tmp[k++] = a[i++]; while( j <= r) tmp[k++] = a[j++]; for( int i = l; i <= r; i++) a[i] = tmp[i]; } void MergeSort( int l, int r)//归并排序 { if( l < r) { int mid = (l+r)>>1; MergeSort(l,mid);//左边排序 MergeSort(mid+1,r);//右边排序 Merge(l,mid,r);//合并 } } int main() { int T; scanf("%d",&T); while( T--) { scanf("%d",&n); for( int i = 0; i < n; i++) scanf("%d",&a[i]); ans = 0; MergeSort(0,n-1); static int cas = 1; printf("Scenario #%d:\n%d\n\n",cas++,ans); } return 0; }
