因为相邻两个数字交换，每次只能减少一个逆序对数量，所以这道题最终的交换次数就等于原序列当中逆序对的数量。
但是因为每个数字的交换代价会随着交换次数而增加，所以虽然我们知道Σ数字交换次数 = 逆序对数量，我们也不能按照传统的逆序对数量统计方式直接计算，这样子会导致我们只知道最终的交换次数，但不知道每个数字的权值。
因此，我们要变相统计逆序对数量，针对每个数字统计他需要进行交换的次数。
本题代码：
#include <iostream> #include <algorithm> using namespace std; const int N = 100005; struct mytype{ int v, cnt; bool operator < (const mytype &tmp) const { return v < tmp.v; } } a[N], tmp[N]; inline int read() { int x = 0; char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x; } int n; void mergesort(int l, int r) { if(l == r) return; int mid = l + r >> 1; mergesort(l, mid); mergesort(mid + 1, r); int i = l, j = mid + 1, k = l; while(i <= mid && j <= r) { if(a[i].v <= a[j].v) { a[i].cnt += j - mid - 1; tmp[k++] = a[i++]; } else { a[j].cnt += mid - i + 1; tmp[k++] = a[j++]; } } while(i <= mid) { a[i].cnt += r - mid; tmp[k++] = a[i++]; } while(j <= r) tmp[k++] = a[j++]; for(int t = l; t <= r; t++) a[t] = tmp[t]; } int main() { n = read(); for(int i = 1; i <= n; i++) { a[i].v = read(); } mergesort(1, n); long long ans = 0; for(int i = 1; i <= n; i++) ans += (long long) a[i].cnt * (a[i].cnt + 1) / 2; cout << ans << endl; system("pause"); return 0; }
可以与“用归并排序统计逆序对”的代码进行比较，加深理解：
#include<bits/stdc++.h> using namespace std; const int N=100005; int n,a[N]; int tmp[N]; void sort(int l,int r) { if(l==r) return ; int mid=l+r>>1; sort(l,mid);sort(mid+1,r); int i=l,j=mid+1,k=l; while(i<=mid&&j<=r) { if(a[i]<=a[j]) tmp[k++]=a[i++]; else tmp[k++]=a[j++]; } 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]; } int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(1,n); for(int i=1;i<=n;i++) printf("%d ",a[i]); return 0; }
在统计逆序对的时候，我们只需要在(a[i]<=a[j])或者(a[i]>a[j])一种情况下进行统计，因为一个逆序对虽然与两个数字有关，但是我们在涉及到其中任何一个数字时，都能算上这个逆序对。
但是在这道题的代码当中，我们在这两种情况里就都需要进行统计，因为一次交换对于它所涉及的两个数字而言，它们的权值都会增加一。