HDU4911 Inversion【逆序偶+归并排序】

Inversion

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

 

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

 

问题链接：HDU4911 Inversion

问题简述：（略）

问题分析：

  可以定义逆序对，一个序列中存在a[i]>a[j]且i<j，则a[i]与a[j]构成一对逆序对。

  一个序列的逆序对的总数，就是这个序列的逆序数。

  相邻元素进行交换，那么每次交换序列逆序数必然改变1，而一个递增的序列逆序数为0。因此，最少交换次数即为逆序数，而每次按照逆序对减少的方式交换就得到递增序列。

  这个程序必须采用基于分治法的排序算法程序，以便保证时间复杂度为O(nlogn)。

程序说明：

  需要注意变量cnt，当数据多的时候，需要声明为long long类型，以免数据溢出。

  程序使用标准的归并排序程序修改而成，只是增加了第19行。

  这次写的程序，把16行改为<=（原先是<）。这个是必要的，如果数的序列中出现相同值，这里是需要改的。

题记：（略）

参考链接：归并排序（分治法）

 

AC的C语言程序如下：

/* HDU4911 Inversion */

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5;
int a[N], temp[N];
long long cnt;

void merge(int low, int mid, int high)
{
    int i = low, j=mid+1, k = low;
    while(i <= mid && j <= high)
    {
        if(a[i] <= a[j])
            temp[k++] = a[i++];
        else {
            cnt += j - k;
            temp[k++] = a[j++];
        }
    }
    while(i <= mid)
        temp[k++] = a[i++];
    while(j <= high)
        temp[k++] = a[j++];
    for(i=low; i<=high; i++)
         a[i] = temp[i];
}

void mergesort(int low, int high)
{
    if(low < high)
    {
        int middle = (low + high) / 2;
        mergesort(low, middle);
        mergesort(middle+1, high);
        merge(low, middle, high);
    }
}

int main()
{
    int n, k;
    while(~scanf("%d%d", &n, &k)) {
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);

        cnt = 0;
        mergesort(0, n - 1);

        printf("%lld\n", cnt > k ? cnt - k : 0);
    }

    return 0;
}