题目链接：hdu 4911 Inversion

题目大意：给定一个序列，有k次机会交换相邻两个位置的数，问说最后序列的逆序对数最少为多少。

解题思路：每交换一次一定可以减少一个逆序对，所以问题转换成如何求逆序对数。

#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long ll; const int maxn = 1e5+5; ll k; int n, s[maxn], t[maxn]; ll merge_sort (int l, int r, int* a, int* b) { if (l == r) return 0; int mid = (l + r) / 2; ll ret = merge_sort(l, mid, a, b) + merge_sort(mid+1, r, a, b); int mvl = l, mvr = mid+1, mv = l; while (mvl <= mid || mvr <= r) { if (mvr > r || (mvl <= mid && a[mvl] <= a[mvr])) { b[mv++] = a[mvl++]; } else { ret += mid - mvl + 1; b[mv++] = a[mvr++]; } } for (int i = l; i <= r; i++) a[i] = b[i]; return ret; } int main () { while (scanf("%d%I64d", &n, &k) == 2) { for (int i = 1; i <= n; i++) scanf("%d", &s[i]); ll ans = merge_sort(1, n, s, t); printf("%I64d\n", max(ans - k, 0LL)); } return 0; }