Inversion

3 1
2 2 1
3 0
2 2 1

1
2

题目大意：

有n个数，问你经过K次交换后的逆序数最少多少个？

根据排序的思想，每一步都能减少1个逆序数，所以K步之多减少K个逆序数。

因此，这题转化为了求逆序数，数据量略微大，用归并排序即可。

解题代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=110000;
int n,m,d[maxn];
typedef long long ll;

ll query(int l,int r){
    if(l>=r) return 0;
    else if(l+1==r){
        if(d[r]>=d[l]) return 0;
        else return 1;
    }
    else{
        int mid=(l+r)/2;
        ll ret=query(l,mid)+query(mid+1,r);
        sort(d+l,d+mid+1);
        for(int i=mid+1;i<=r;i++){
            ret+=(int)( (d+mid+1) - upper_bound(d+l,d+mid+1,d[i]) );
        }
        return ret;
    }
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<n;i++) scanf("%d",&d[i]);
        ll ans=query(0,n-1);
        if(ans<=m) printf("0\n");
        else cout<<ans-m<<endl;
    }
    return 0;
}

HDU 4911 Inversion（基本算法-排序）,布布扣,bubuko.com

HDU 4911 Inversion（基本算法-排序）

原文：http://blog.csdn.net/a1061747415/article/details/38424455