离散化，树状数组，逆序数。
有$k$次机会交换相邻的数，因为只能交换相邻的数，所以只要逆序对还有，就必然可以通过交换相邻的数消灭一个逆序对。
因此，问题就简单了，只要算出原来的逆序对有多少，然后减去$k$就是答案，要注意的是，减去$k$之后如果$<0$了，那么答案为$0$。
因为$a[i]$较大，所以求逆序数的时候要先把数字先离散化一下。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } const int maxn=100010; int a[maxn],b[maxn],c[maxn],n; LL k; int get(int x) { int res,L=1,R=n; while(L<=R) { int mid=(L+R)/2; if(b[mid]>x) R=mid-1; else if(b[mid]==x) res=mid, R=mid-1; else L=mid+1; } return res; } int lowbit(int x) { return x&(-x); } void update(int p,int v) { while(p<=n) c[p]=c[p]+v,p=p+lowbit(p); } int sum(int p) { int res=0; while(p>0) res=res+c[p],p=p-lowbit(p); return res; } int main() { while(~scanf("%d%lld",&n,&k)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); for(int i=1;i<=n;i++) a[i]=get(a[i]); LL ans=0; memset(c,0,sizeof c); for(int i=1;i<=n;i++) { ans=ans+sum(n)-sum(a[i]); update(a[i],1); } printf("%lld ",max((LL)0,ans-k)); } return 0; }