大意:将无序的序列通过两两交换最少需要几次才能有序。
思路:可以证明即数列的逆序对数,于是归并排序求解。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> using namespace std; const int MAXN = 500010; int n; typedef long long LL; LL A[MAXN], T[MAXN]; void merge_sort(int x, int y, LL &ans) { if(y-x > 1) { int m = x + (y-x)/2; int p = x, q = m, i = x; merge_sort(x, m, ans); merge_sort(m, y, ans); while(p < m || q < y) { if(q >= y || (p < m && A[p] < A[q])) T[i++] = A[p++]; else { T[i++] = A[q++]; ans += (m - p); } } for(i = x; i < y; i++) A[i] = T[i]; } } int read_case() { scanf("%d", &n); if(!n) return 0; for(int i = 0; i < n; i++) scanf("%lld", &A[i]); return 1; } void solve() { LL ans = 0; merge_sort(0, n, ans); printf("%lld\n", ans); } int main() { while(read_case()) { solve(); } return 0; }