题解:
题意:
给你n个数,允许相邻的交换k次,问你能得到的最小逆序对数
思路:
一开始想用树状数组来求逆序对。。后来发现1e9就放弃了。。老老实实归并排序吧,max(逆序对数减去交换次数,0)就是答案,注意要long long
代码:
#include<iostream> #include<cstring> #include<stdio.h> #include<math.h> #include<string> #include<stdio.h> #include<queue> #include<stack> #include<map> #include<vector> #include<deque> #include<algorithm> using namespace std; #define INF 100861111 #define ll long long #define eps 1e-15 int a[100005]; int t[100005]; ll ans; void Merge(int l,int r,int mid) { int i=l,j=mid+1,k=l; while(i<=mid&&j<=r) { if(a[i]>a[j]) { ans+=(mid+1-i); t[k]=a[j]; j++; } else { t[k]=a[i]; i++; } k++; } while(i<=mid) { t[k]=a[i]; i++; k++; } while(j<=r) { t[k]=a[j]; k++; j++; } for(i=l;i<=r;i++) a[i]=t[i]; } void guibin(int l,int r) { if(l<r) { int mid=(l+r)/2; guibin(l,mid); guibin(mid+1,r); Merge(l,r,mid); } } int main() { int i,j,n,x; ll k; while(scanf("%d%lld",&n,&k)!=EOF) { ans=0; for(i=0;i<n;i++) { scanf("%d",&a[i]); } guibin(0,n-1); ans=max(ans-k,(ll)0); printf("%lld\n",ans); } return 0; }