Problem 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
Author
Xiaoxu Guo (ftiasch)
Source
2014 Multi-University Training Contest 5
【题解】
水题，不过题意比较模糊，给一个序列，每次可以交换相邻的逆序数（i<j&&a[i]?a[j]），
并且最多交换k次，问交换完的最小逆序对个数。
思考一下，每次只交换相邻两个，所以也就是说每次只会减少一个逆序对，所以就是把最初的逆序数对求出来减去k即为答案。
注意要用 long long
【AC代码】
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e5+5;
int n,node[N],m[N],str[N];
__int64 ss,mins;void Mergee(int first,int mid,int end,int a[])
{int i=first;int j=mid+1;int k=first;while(i<=mid && j<=end){if(a[i]>a[j]){m[k++]=a[j++];ss += mid - i+1 ;}else{m[k++]=a[i++];}}while(i<=mid){m[k++]=a[i++];}while(j<=end){m[k++]=a[j++];}for(int i=first;i<=end;i++)a[i]=m[i];
}void MergeSort(int first,int end,int a[])
{if(first<end){int mid = (first+end)>>1;MergeSort(first,mid,a);MergeSort(mid+1,end,a);Mergee(first,mid,end,a);}
}int main()
{int k;while(~scanf("%d%d",&n,&k)){for(int i=1;i<=n;i++){scanf("%d",&node[i]);}ss=0;MergeSort(1,n,node);mins=ss;printf("%I64d\n",max(mins-k,(__int64)0));}return 0;
}