HDOJ 4911-Inversion【逆序对模板】

太过爱你忘了你带给我的痛 2022-07-24 10:13 20阅读 0赞

# Inversion #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)  
Total Submission(s): 3201 Accepted Submission(s): 1173**

Problem 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 1
    2 2 1
    3 0
    2 2 1

Sample Output

1
    2

Author

Xiaoxu Guo (ftiasch)

解题思路：

题意：给出n个数，每次可以交换相邻的两个数，最多交换k次，求交换后最小的逆序数是多少。

分析：如果逆序数大于0，则存在1 ≤ i < n，使得交换ai和ai+1后逆序数减1。所以最后的答案就是max((inversion-k), 0)。利用归并排序求出原序列的逆序对数就可以解决问题了。

#include<stdio.h>
    #include<string.h>
    #define N 100005
    __int64 cnt, k;
    int a[N],c[N];
    void merge(int a[], int first, int mid, int last, int c[])
    {
        int i = first, j = mid + 1;
        int m = mid, n = last;
        int k = 0;
        while(i <= m || j <= n)
        {
            if(j > n || (i <= m && a[i] <= a[j]))
                c[k++] = a[i++];
            else
            {
                c[k++] = a[j++];
                cnt += (m - i + 1);
            }
        }
        for(i = 0; i < k; i++)
            a[first + i] = c[i];
    }
    void merge_sort(int a[], int first, int last, int c[])
    {
        if(first < last)
        {
            int mid = (first + last) / 2;
            merge_sort(a, first, mid, c);
            merge_sort(a, mid+1, last, c);
            merge(a, first, mid, last, c);
        }
    }
    int main()
    {
        int n;
        while(~scanf("%d%I64d",&n,&k))
        {
            memset(c, 0, sizeof(c));
            cnt = 0;
            for(int i = 0; i < n; i++)
                scanf("%d", &a[i]);
            merge_sort(a, 0, n-1, c);
            if(k >= cnt) cnt = 0;
            else cnt -= k;
            printf("%I64d\n",cnt);
        }
    }