首页 > 代码库 > HDU 4911 Inversion

HDU 4911 Inversion

2024-08-11 02:52:33   217人阅读

Time Limit:1000MS     Memory Limit:131072KB     64bit IO Format:%I64d & %I64u
Submit Status Practice HDU 4911

Description

bobo has a sequence a 1,a 2,…,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 5,0≤k≤10 9). The second line contains n integers a 1,a 2,…,a n (0≤a i≤10 9).

Output

For each tests: 

A single integer denotes the minimum number of inversions.

Sample Input

3 12 2 13 02 2 1

Sample Output

12
/*归并排序求逆序对对数，然后减去可以交换的次数因为数据范围有10^9，所以逆序对的个数可能超过int类型*/#include <iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n;long long k,ans;int a[100005],b[100005];void work(int l,int mid,int r){    int i=l,j=mid+1;    int len=0;    while(i<=mid && j<=r)    {        if (a[i]>a[j])        {            b[++len]=a[j++];            ans+=mid-i+1;        } else b[++len]=a[i++];    }    while(i<=mid) b[++len]=a[i++];    while(j<=r) b[++len]=a[j++];    for(int i=1;i<=len;i++) a[l+i-1]=b[i];}void guibing(int l,int r){    int mid;    if (l>=r) return;     mid=(l+r)/2;     guibing(l,mid);     guibing(mid+1,r);     work(l,mid,r);}int main(){    while(~scanf("%d%lld",&n,&k))    {        ans=0;        for(int i=1;i<=n;i++) scanf("%d",&a[i]);        guibing(1,n);        printf("%lld\n",ans-k>0?ans-k:0);    }    return 0;}

 

HDU 4911 Inversion


联系
我们