CF1930C Lexicographically Largest 题解

前言

很有意思的一道题。

做法参考了 CF 官方题解。

思路

考虑进行一次操作会对其他元素造成的影响。

删除 $a_i$ 会使其右边的所有元素下标减少 $1$，而我们的任务是让最后得到的集合 $S$ 字典序最大，所以我们希望每个数的下标都尽量不要减少。

但问题在于 $S$ 并不是一个可重集，故我们不能直接从右往左执行操作，因为这样给 $S$ 带来的元素虽然是最大的，但可能会出现重复的情况，例如样例里的 2 1，如果先删右边的 $1$ 再删 $2$ 就会带来两个重复的 $3$，去重后字典序小于答案 3 2。

于是我们可以考虑每个数的下标减小了几次，记作 $c_i\ (0\leq c_i<i)$，则任务就变成了对于每个 $a_i$ 找到最小的 $c_i$，使得对于任意 $j<i$，$a_i+i-c_i≠a_j+j-c_j$。发现无论求解 $c_i$ 的顺序如何，答案最优性都不会受到影响。

同时，由于 $c_1=0$，如果 $a_1$ 在 $a_2$ 之前删除则 $c_2=1$（反之 $c_2=0$），继续推导可得任意一个满足 $0\leq c_i<i$ 的序列 $c$ 都是可以被某种操作顺序构造出来的，于是答案的可行性也得到了保证。

现在的问题就变成了怎么找当前最小的 $c_i$，满足 $a_i+i-c_i$ 还没有在答案里出现过。

如果对于所有 $c_i\in [0,x)$，$a_i+i-c_i$ 都出现过，则存在$j<i$ 使得 $a_i+i-(x-1)=a_j+j+c_j$ 且不存在 $k<i$ 使 $a_i+i-x=a_k+k-c_k$。第一个式子可以化简为 $a_i+i-x=a_j+j+c_j-1$。也就是说，当前的答案 $v_i$ 只有两种情况，如果是 $a_i+i$ 没有出现过则 $c_i=0$，$v_i$ 直接等于 $a_i+i$，否则 $v_i=\max\{v_j-1\}\ (j<i,a_i+i\leq v_j-1)$。

实现方面可以用两个 set 维护之前出现过的答案和待选的答案集合，如果 $a_i+i$ 出现过就在待选的集合里二分查找需要的答案。

于是这道题我们就做完了，代码比较好写。

代码

void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        a[i]+=i;
        }
    vector<ll> sol;
    set<ll> vis,now;
    for(int i=1;i<=n;i++){
        ll v;
        if(!vis.count(a[i])) v = a[i];
        else{
            auto it = now.upper_bound(a[i]);it--;
            v = *it;
        }
        sol.pb_(v);
        vis.insert(v);now.erase(v);
        if(!vis.count(v-1)) now.insert(v-1);
    }
    sort(sol.begin(),sol.end(),greater<ll>());
    for(ll i:sol) cout<<i<<" ";
    cout<<"\n";
}