HDU 4911 Inversion

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4911
题记：归并排序的训练。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll a[N],b[N],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(){
    ll n,k;
    while(~scanf("%lld%lld",&n,&k)){
        cnt=0;//初始化
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        Mergesort(0,n-1);
        if(cnt<=k)
            printf("0\n");
        else
            printf("%lld\n",cnt-k);
    }
    return 0;
}