Mex vs Diff

pengyule · 2022-11-14 14:32:06 · 题解

有两种操作：

1. 用后面的数填补当前的 mex，以增大 mex
2. 把后面的数合并到已经有的数上，以减小 diff

就单次操作的贡献而言，前者的贡献至少为 1，后者的贡献至多为 1，因而优先考虑操作 1。
这部分代码如下：

for(int i=1;i<=n;i++)a[i]=read(),mp[a[i]]++;
int mex=0,Need=0,Already=0;
for(int i=0;i<=n;i++){
    if(i)Already+=!!mp[i-1];
    if(i&&!mp[i-1]){
        Need++;
        if(Need>K||Need>n-Already)break;
    }
    mex=i;
}

现在我们已经确定了 mex，只需对 \ge mex 的位上的数使用操作 2，按照出现次数从小到大的顺序操作。
这部分代码如下：

vector<int>vec;
for(map<int,int>::iterator it=mp.lower_bound(mex);it!=mp.end();it++)
    vec.push_back(it->second);
sort(vec.begin(),vec.end());
int diff=vec.size();
for(int i:vec){
    if(K>=i)K-=i,diff--;
    else break;
}
cout<<diff<<'\n';