首页 > 代码库 > HDU4911：Inversion

HDU4911：Inversion

2024-07-16 01:59:19   220人阅读

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


根据逆序数的定理
如果逆序数大于0，那么必定存在1<=i<n使得i和i+1交换后逆序数减1
假设原逆序数为cnt，这样的话，我们就可以得到答案是max（cnt-k,0）
求逆序数可以用归并的方法
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int a[100005];
int left[100005], right[100005];
__int64 cnt;

void merge(int* a, int p, int q, int r)
{
    int i, j, k, n1, n2;
    n1 = q-p+1;
    n2 = r-q;
    for (i=0; i<n1; i++)
    {
        left[i] = a[p+i];
    }
    for (i=0; i<n2; i++)
    {
        right[i] = a[q+i+1];
    }
    left[n1] = right[n2] = 0x7fffffff;

    i = j = 0;
    for (k=p; k<=r; k++)
    {
        if (left[i] <= right[j])
        {
            a[k] = left[i];
            i++;
        }
        else
        {
            a[k] = right[j];
            j++;
            cnt += n1-i; /**此步骤是在归并排序法中加的一句，用来计数求逆序数的数目**/
        }
    }
    return;
}

void mergesort(int* a, int p, int r)
{
    int q;
    if (p < r)
    {
        q = (p+r)/2;
        mergesort(a, p, q);
        mergesort(a, q+1, r);
        merge(a, p, q, r);
    }
    return ;
}
int main()
{
    int n,k,i,j;
    while(~scanf("%d%d",&n,&k))
    {
        cnt = 0;
        for(i = 0;i<n;i++)
        scanf("%d",&a[i]);
        mergesort(a,0,n-1);
        printf("%I64d\n",max(cnt-k,(__int64)0));
    }

    return 0;
}



联系
我们