?
给出n个数，每次只能交换两个相邻的数，问使得n个数有序最少需要交换多少次。
归并排序的模板，重在理解，小白书p144.
#include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 using namespace std; const int maxn = 500010; LL cnt; int n,a[maxn],t[maxn]; void merge_sort(int *a, int x, int y, int *t) { if(y-x > 1) { int m = x + (y-x)/2; int p = x,q = m,i = x; merge_sort(a,x,m,t); merge_sort(a,m,y,t); while(p < m || q < y) { if(q >= y || (p < m && a[p] <= a[q])) t[i++] = a[p++]; else { t[i++] = a[q++]; cnt += m-p; } } for(i = x; i < y; i++) a[i] = t[i]; } } int main() { while(~scanf(%d,&n)&&n) { for(int i = 0; i < n; i++) scanf(%d,&a[i]); cnt = 0; merge_sort(a,0,n,t); printf(%lld ,cnt); } return 0; }