Description
bobo has a sequence a
1,a
2,…,a
n. 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 a i>a j.
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 a i>a j.
Input
The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤10 5,0≤k≤10 9). The second line contains n integers a 1,a 2,…,a n (0≤a i≤10 9).
The first line contains 2 integers n,k (1≤n≤10 5,0≤k≤10 9). The second line contains n integers a 1,a 2,…,a n (0≤a i≤10 9).
Output
For each tests:
A single integer denotes the minimum number of inversions.
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 <stdio.h>
#define N 150000
int a[N],tmp[N];
long long ans;//
void Merge(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; //这里加上相应的数
}
else
{
tmp[k++]=a[i++];
}
}
while(j<=r) tmp[k++]=a[j++];
while(i<=m) tmp[k++]=a[i++];
for(int i=l;i<=r;i++)
a[i]=tmp[i];
}
void Merge_sort(int l,int r)
{
if(l<r)
{
int m=(l+r)>>1;
Merge_sort(l,m);
Merge_sort(m+1,r);
Merge(l,m,r);
}
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
ans=0;
Merge_sort(0,n-1);
ans-=k;
if(ans<0)ans=0;
printf("%I64d\n",ans);
}
return 0;
}