3 1 2 2 1 3 0 2 2 1
1 2
题意：求经过最多k次相邻的交换的操作，使得序列的逆序数对最小是多少
思路：线段树和树状数组都开不下，然后就用归并排序的方法得到当前序列的逆序数对，然后就是想如果想得到最小的话，那么我们每次能的是把大的数放到后面，这样逆序数会减一，然后就能得到答案了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn], b[maxn<<1];
int n, k;
ll ans;
void msort(int s, int t) {
int mid = (s + t) >> 1;
int qb = 1, bn = t-s+1;
if (s >= t)
return;
msort(s, mid);
msort(mid+1, t);
int i, j;
for (i = s, j = mid+1; i <= mid && j <= t; ) {
if (a[i] <= a[j]) {
b[qb] = a[i];
i++;
}
else {
b[qb] = a[j];
ans += mid-i+1;
j++;
}
qb++;
}
while (i <= mid)
b[qb++] = a[i++];
while (j <= t)
b[qb++] = a[j++];
for (i = 1, j = s; i < qb; i++, j++)
a[j] = b[i];
}
int main() {
while (scanf("%d%d", &n, &k) != EOF) {
ans = 0;
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
msort(1, n);
cout << max((ll)0, ans-k) << endl;
}
return 0;
}HDU - 4911 Inversion,布布扣,bubuko.com
原文：http://blog.csdn.net/u011345136/article/details/38390115