本文共 2900 字，大约阅读时间需要 9 分钟。
3 12 2 13 02 2 1
1 2 #define N 100005long long cnt, k;int a[N],c[N];//归并排序的合并操作void merge(int a[], int first, int mid, int last, int c[]){ int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while(i <= m || j <= n) { if(j > n || (i <= m && a[i] <= a[j])) c[k++] = a[i++]; else { c[k++] = a[j++]; cnt += (m - i + 1); } } for(i = 0; i < k; i++) a[first + i] = c[i];}//归并排序的递归分解和合并void merge_sort(int a[], int first, int last, int c[]){ if(first < last) { int mid = (first + last) / 2; merge_sort(a, first, mid, c); merge_sort(a, mid+1, last, c); merge(a, first, mid, last, c); }}int main(){ int n; while(~scanf("%d%lld",&n,&k)) { memset(c, 0, sizeof(c)); cnt = 0; for(int i = 0; i < n; i++) scanf("%d", &a[i]); merge_sort(a, 0, n-1, c); if(k >= cnt) cnt = 0; else cnt -= k; printf("%lld\n",cnt); } return 0;} 树状数组做法 #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; } 转载地址：http://bvali.baihongyu.com/