Problem Description bobo has a sequence a1,a2,…,an. He is allowed to swap two adjacent numbers for no more than k times.
Find the minimum number of inversions after his swaps.
Note: The number of inversions is the number of pair (i,j) where 1≤i < j ≤n and ai>aj.
Input The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an (0≤ai≤109).
Output For each tests:
A single integer denotes the minimum number of inversions.
Sample Input 3 1 2 2 1 3 0 2 2 1
Sample Output 1 2
#include<iostream> #include<algorithm> #include<stdlib.h> using namespace std; int a[100010],tmp[100010]; long long ans; void ld(int l,int m,int r) { int i=l; int j=m+1; int k=l; while(i<=m&&j<=r) { if(a[i]>a[j]) { tmp[k++]=a[j++]; ans+=m-i+1; } if(a[i]<=a[j]) { tmp[k++]=a[i++]; } } while(i<=m) tmp[k++]=a[i++]; while(j<=r) tmp[k++]=a[j++]; for(int i=l;i<=r;i++) a[i]=tmp[i]; } void sort2(int l,int r) { if(l<r) { int m=(l+r)>>1; sort2(l,m); sort2(m+1,r); ld(l,m,r); } } int main() { int n,k; while(cin>>n>>k) { for(int i=1;i<=n;i++) { cin>>a[i]; } ans=0; sort2(1,n); if(ans-k<0) cout<<'0'<<endl; else cout<<ans-k<<endl; } system("pause"); return 0; }