CF1883G2 Dances (Hard Version)

One_JuRuo · 2023-10-23 13:45:11 · 题解

思路

大体上的思路应该和简单版本一致，建议先看本人关于简单版本的题解。

与简单版本不同的是，困难版本的 m 可以不为 1，而是取遍 [1,m] 中的整数，所以答案的总值会变大很多倍。

如果直接枚举 m 次，时间复杂度将会达到 O(mn\log n) 显然过不了，就算优化排序的复杂度，也是 O(mn)，还是过不了。

所以需要思考如何优化。

可以发现，无论第一个值取几，很多之前匹配成功的还是能匹配，所以我们考虑先不管 a_1，把剩下的先匹配了。

因为这里 a 要少一个，所以我换了个思路，改成了用 b 匹配 a，但实际上是一样的，只是我感觉这样写代码要方便一些。

那么，现在来讨论，如果 a_1 小于没被匹配的最大的 b 的话，就可以再匹配一个，也就是操作数少一个。

如果 a_1 大于等于没被匹配的最大的 b 的话，操作数就会多一个。

假设不算 a_1 匹配的个数是 i，没被匹配的最大的 b 是 b_k 的话，答案就应该是 (n-i-1)\times m+\max(0,m-b_k+1)。（取 \max 是因为可能 m 很小，b_k 很大，就会导致后面是负的）

AC code

#include<bits/stdc++.h>
using namespace std;
long long T,n,m,a[100005],b[100005],ans,maxn;
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m),ans=0;
        for(long long i=1;i<n;++i) scanf("%lld",&a[i]);
        for(long long i=1;i<=n;++i) scanf("%lld",&b[i]);
        sort(a+1,a+n),sort(b+1,b+n+1);
        long long j=1,flag=0;maxn=0;
        for(long long i=1;i<n;++i)
        {
            while(j<n&&a[i]>=b[j]) maxn=max(maxn,b[j]),++j;
            if(j==n)
            {
                flag=1;
                if(a[i]<b[j]) ans=m*(n-i-1)+max(0ll,m-maxn+1);
                else ans=m*(n-i)+max(0ll,m-max(maxn,b[j])+1);
                break;
            }
            ++j;
        }
        if(!flag) ans=max(0ll,m-b[n]+1);
        printf("%lld\n",ans);
    }
    return 0;
}