裸的 树状数组 + 离散化
对一个数列进行K次 移动 求最后的逆序对有多少,其实就是求k次操作后最少的逆序数多少
每次的swap 操作 只能和相邻的交换 例如a b 如果a > b 那么a b就交换 整个数列 逆序数-1
n个数 只需要 x ( x = 逆序数) 次swap 就可以变成单调递增
所以求出原数列逆序数在和k 比较小就可以了。。
注意数据 需要离散化 还有排序的时候
这种题目还是上树状数组比较爽 哈哈
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef __int64 ll; int const MAXN = 100010; int c[MAXN]; struct S{ int v,pos; }a[MAXN]; bool cmp(S x,S y){ if(x.v != y.v) return x.v < y.v; return x.pos < y.pos; } int LowBit(int x){ return x&(-x); } void Add(int x,int d){ while(x < MAXN){ c[x] += d; x += LowBit(x); } } ll Sum(int x){ ll ret = 0; while(x > 0){ ret += c[x]; x -= LowBit(x); } return ret; } int main(){ int n,k; while(~scanf("%d%d",&n,&k)){ memset(c,0,sizeof(c)); for(int i = 1;i <= n;i++){ scanf("%d",&a[i].v); a[i].pos = i; } sort(a + 1,a + n + 1,cmp); ll s = 0; for(int i = 1;i <= n;i++){ Add(a[i].pos,1); s += i - Sum(a[i].pos); } if(k >= s)printf("0\n"); else printf("%I64d\n",s - k); } return 0; }