题意：一个由n个非负整数组成的序列，问进行最多k次相邻交换后最少的逆序对数 (1 ≤ n ≤ 10^5, 0 ≤ k ≤ 10^9, 0 ≤ ai ≤ 10^9)。。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4911
——>>每次只能交换相邻的两个数，每次交换，只改变这两个数的逆序，其他的数对于这两个数的逆序没有改变，所以，求出所有的逆序对，再减去k就是答案。
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int MAXN = 100000 + 10;int n, k;
int a[MAXN], b[MAXN];
long long C[MAXN];void Init()
{memset(C, 0, sizeof(C));
}void Read()
{for (int i = 0; i < n; ++i){scanf("%d", a + i);}
}int Lowbit(int x)
{return x & (-x);
}long long Sum(int x)
{long long nRet = 0;while (x > 0){nRet += C[x];x -= Lowbit(x);}return nRet;
}void Add(int x)
{while (x <= n){C[x]++;x += Lowbit(x);}
}void Solve()
{int nCnt = 0;int nId = 0;long long nReverse = 0;memcpy(b, a, sizeof(a));sort(b, b + n);nCnt = unique(b, b + n) - b;for (int i = n - 1; i >= 0; --i){nId = lower_bound(b, b + nCnt, a[i]) - b + 1;nReverse += Sum(nId - 1);Add(nId);}if (nReverse > k){nReverse -= k;}else{nReverse = 0;}printf("%I64d\n", nReverse);
}int main()
{while (scanf("%d%d", &n, &k) == 2){Init();Read();Solve();}return 0;
}