HDU 4911 Inversion（求逆序对）_综合

bobo has a sequence a ₁,a ₂,…,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.

Input

The input consists of several tests. For each tests:

The first line contains 2 integers n,k (1≤n≤10 ⁵,0≤k≤10 ⁹). The second line contains n integers a ₁,a ₂,…,a _n (0≤a _i≤10 ⁹).

Output

For each tests:

A single integer denotes the minimum number of inversions.

Sample Input

Sample Output

1
2

题解：

题意：

给你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;
}