程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4911 Inversion(歸並排序求逆序對數)

hdu 4911 Inversion(歸並排序求逆序對數)

編輯:C++入門知識

hdu 4911 Inversion(歸並排序求逆序對數)


Inversion

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

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≤ii>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
題意:給出n個數,每次可以交換相鄰的兩個數,最多交換k次,求交換後最小的逆序數是多少。 分析:如果逆序數大於0,則存在1 ≤ i < n,使得交換ai和ai+1後逆序數減1。所以最後的答案就是max((inversion-k), 0)。利用歸並排序求出原序列的逆序對數就可以解決問題了。
#include
#include
#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);
    }
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved