HDU 4911 Inversion（求逆序对）

逃离我推掉我的手 2022-06-09 08:43 181阅读 0赞

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

题解：

题意：

给你n个数，允许相邻的交换k次，问你能得到的最小逆序对数

思路：

一开始想用树状数组来求逆序对。。后来发现1e9就放弃了。。老老实实归并排序吧，max(逆序对数减去交换次数,0)就是答案，注意要long long

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-15
    int a[100005];
    int t[100005];
    ll ans;
    void Merge(int l,int r,int mid)
    {
        int i=l,j=mid+1,k=l;
        while(i<=mid&&j<=r)
        {
            if(a[i]>a[j])
            {
                ans+=(mid+1-i);
                t[k]=a[j];
                j++;
            }
            else
            {
                t[k]=a[i];
                i++;
            }
            k++;
        }
        while(i<=mid)
        {
            t[k]=a[i];
            i++;
            k++;
        }
        while(j<=r)
        {
            t[k]=a[j];
            k++;
            j++;
        }
        for(i=l;i<=r;i++)
            a[i]=t[i];
    }
    void guibin(int l,int r)
    {
        if(l<r)
        {
            int mid=(l+r)/2;
            guibin(l,mid);
            guibin(mid+1,r);
            Merge(l,r,mid);
        }
    }
    int main()
    {
        int i,j,n,x;
        ll k;
        while(scanf("%d%lld",&n,&k)!=EOF)
        {
            ans=0;
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            guibin(0,n-1);
            ans=max(ans-k,(ll)0);
            printf("%lld\n",ans);
        }
        return 0;
    }