HDU 4911 Inversion
归并排序
求逆序对数量
AC代码
#include<iostream>
#include<cstdio>#include<cstring>
#include<bitset>
#include<sstream>
#include<string.h>
#include<iomanip>#include<cmath>
#include<algorithm>
#include<cstdlib>#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
#define ll long long
const ll inf=0x3f3f3f3f;
typedef pair<int ,int > PII;
const int maxn=1e5+10;
ll a[maxn],b[maxn],cnt;
void merge(ll l,ll mid ,ll r){
ll i=l,j=mid+1,t=0;while(i<=mid&j<=r){
if(a[i]>a[j]){
b[t++]=a[j++];cnt+=mid-i+1;}else{
b[t++]=a[i++];}}while(i<=mid)b[t++]=a[i++];while(j<=r)b[t++]=a[j++];for(i= 0; i<t;i++)a[l+i]=b[i];
}
void mergesort(ll l ,ll r){
if(l<r){
ll mid=(l+r)/2;mergesort(l,mid);mergesort(mid+1,r);merge(l,mid,r);}
}
int main(){
#define io#ifdef iofreopen("in.txt","r",stdin);#endifll n,k;while(~scanf("%lld%lld",&n,&k)){
cnt=0;for(ll i=0;i<n;i++)scanf("%lld",&a[i]);mergesort(0,n-1);if(cnt<=k)cout<<0<<endl;else printf("%lld\n",cnt-k); }return 0;
}