首页 > 代码库 > hdu 4911 Inversion

hdu 4911 Inversion

2024-07-15 23:57:38   224人阅读

Inversion

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 197    Accepted Submission(s): 82


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
 



题解及代码：


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
__int64 ans=0;

void merge(int Array[],int l,int m,int r)
{
    int temp[100110];
    int i=l,j=m+1,k=0;
    while(i<=m&&j<=r)
    {
        if(Array[i]<=Array[j])
        {
            temp[k++]=Array[i];
            i++;
        }
        else
        {
            temp[k++]=Array[j];
            j++;
            ans+=(m-i+1);     //求逆序数的关键
        }
    }
    while(i<=m) {temp[k++]=Array[i];i++;}
    while(j<=r) {temp[k++]=Array[j];j++;}

    for(i=l,j=0;i<=r&&j<k;i++,j++)
    {
        Array[i]=temp[j];
    }
}

void mergesort(int Array[],int l,int r)
{
    if(l>=r) return;
    int m=(l+r)/2;

    mergesort(Array,l,m);
    mergesort(Array,m+1,r);

    merge(Array,l,m,r);
}

int main()
{
    int n,k;
    int Array[100110];
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        ans=0;
        for(int i=0;i<n;i++)
        {
            cin>>Array[i];
        }
        mergesort(Array,0,n-1);
        if(k>=ans)
        {
            printf("0\n");
        }
        else printf("%I64d\n",ans-k);
    }
    return 0;
}
/*
简单题，本题主要是求出当前数列的逆序数。

我们直到每次调序都能将逆序数减少1，我们先求出逆序数，
然后判断，当给出的调序次数小于当前序列的逆序数时，输出ans-k，
否则输出0。
*/


联系
我们