首页 > 代码库 > HDU 4911 Inversion（基本算法-排序）

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

2024-07-16 10:53:23   221人阅读

Inversion



Problem Description
bobo has a sequence a1,a2,…,an. 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 ai>aj.
 

Input
The input consists of several tests. For each tests:

The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an (0≤ai≤109).
 

Output
For each tests:

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
 

Recommend
We have carefully selected several similar problems for you:  4930 4929 4928 4927 4926 
 

题目大意：

有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;
}



联系
我们