题意：一个由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 
  
   
#include 
   
     #include 
    
      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; }