题解：P14507 缺零分治 mexdnc

· · 题解

题意简述

有 n 种非负整数 a_i，其中 a_i 有 b_i 个。有 q 次询问，每次给定 m，问最少将这些数分进几个可重集合，可以使每个集合的 \operatorname{mex} 之和恰好为 m，或判断无解。

题目分析

显然 a_i\ge n 是无用的，输入时判掉即可。

我们先特判掉 a_1\not=0 的情况，此时当且仅当 m=0 时有解且 k=1，否则无解。

考虑其它情况什么时候无解。当 m=0 时，显然无解。当 m 超过可能的 \operatorname{mex} 之和的最大值时，显然也无解。

考虑什么时候答案为 1。显然当且仅当整个序列的 \operatorname{mex} 为 m 时，答案为 1。

考虑一般情况。对于 a_i，若要其产生贡献，则该集合中必须包含 a_i-1。于是每个集合都相当于一串 0,1,\dots,x 再加上一些冗余部分。我们先求出 \operatorname{mex} 之和的最大值，设其为 c。考虑贪心，显然将多于一个 0 放在一个集合里是不优的，所以每个 0 占一个集合。然后把 1 放进尽可能多的有 0 的集合，把 2 放进尽可能多的有 1 的集合……这个过程可以用单调栈来维护，在栈中存下 a_i 递增，b_i 递减的二元组 (a_i,b_i) 即可。

注意到在上述过程中，每步最多将所有集合的 \operatorname{mex} 之和增加 1，所以 1\sim c 中的每个 m 都是可以表示出来的。但是这样不一定是最优解。考虑更换顺序，按照 \operatorname{mex} 递减的顺序填充集合。

于是我们就可以愉快地二分了！每次将 \operatorname{mex} 较大的几个集合取出，最后一个集合可能只取一部分，然后把多余的数塞进第一个集合。为什么这样是对的呢？假设有一组更优的解，不难发现把其中 \operatorname{mex} 最大的集合扩展至最大，然后把其它集合中的若干个元素移到 \operatorname{mex} 最大的集合，答案不会变大，由数学归纳法即可证明贪心的正确性。注意特判 m 小于 \operatorname{mex} 最大的集合的 \operatorname{mex} 的情况，此时只能把 <m 的元素放进一个集合，\ge m 的元素放进令一个集合，故答案为 2。

时间复杂度 O(T(n+q\log n))，空间复杂度 O(n)。

::::success[代码]

#include<bits/stdc++.h>
using namespace std;
long long T,n,q,m,l,r,d,c,z,i,a[100005],b[100005],f[100005],t[100005],p[100005],o[100005];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>q;
        for(i=0;i<=n;i++)f[i]=0;
        for(i=0;i<n;i++){
            cin>>a[i]>>b[i];
            if(a[i]<=n)f[a[i]]+=b[i];
        }
        if(!f[0]){
            while(q--){
                cin>>m;
                if(m)cout<<"-1\n";
                else cout<<"1\n";
            }
            continue;
        }
        for(z=i=1;i<=n;i++)if(f[i]<f[t[z]])t[++z]=i;
        for(i=1;z;i++){
            a[i]=t[z];
            b[i]=f[t[z-1]]-f[t[z]];
            p[i]=p[i-1]+a[i]*b[i];
            o[i]=o[i-1]+b[i];
            c=i;
            z--;
        }
        while(q--){
            cin>>m;
            if(!m||m>p[c])cout<<"-1\n";
            else if(m==p[c])cout<<o[c]<<'\n';
            else if(m==a[1])cout<<"1\n";
            else if(m<a[1])cout<<"2\n";
            else{
                l=1;
                r=c;
                while(l<=r){
                    d=l+r>>1;
                    if(p[d]<m)l=d+1;
                    else r=d-1;
                }
                cout<<o[r]+(long long)ceil((m-p[r])*1.0/a[r+1])<<'\n';
            }
        }
    }
}

::::