CodeForces 1628A Meximum Array

题目传送门

题目大意

给定一个由 $N$ 个数组成的序列 $A$，现要求执行如下操作直至序列 $A$ 为空：

• 从 $A$ 中顺次取出 $k$ 个元素；
• 求出这 $k$ 个元素的 MEX 值；
• 将该值按次序组成一个新的序列 $B$ 。

现要求求出字典序最大的 $B$ 序列。

MEX 值指一个非负整数集合中未出现的最小非负整数。

分析

这个题我第一眼感觉是一个模拟就可以比较完美解决的题目，但数据范围决定了这个题不能用 $O(N{\log }_{2}N)$ 以上的方法去做。而由 MEX 值的定义与字典序最大的要求，我们就必须组一个前面数字较大、总长度要长的 $B$ 序列出来。而注意到要求 $B$ 序列长度要长的要求，我们在截取时应该截取尽可能少的元素。下面说明这个问题的贪心性质：

记截取到某一个前缀的 MEX 值为 $x$。那么如果我们再往后截取一些比 $x$ 大的数，MEX 值不会变而截取的总数变少了，显而易见对答案是不利的；如果往后一个有 $x$，那么 MEX 值就会变大，即对答案有利。所以我们就可以采取贪心算法，每次截取一段时我们先枚举 MEX 值，如果后面有一样的就继续加长一段，否则就截断后截取新一段重复操作。

这样直接做就是 $O(N^2)$ 的，但注意到 $A$ 序列中所有值都比 $N$ 小，所以我们就可以把 $A$ 中每个数按值把它的位置扔进一个桶里，然后用二分找后面有没有数。总时间复杂度为 $O(N{\log }_{2}N)$。

参考代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MaxN = (int)2e5;

int N, A[MaxN + 5];
vector<int> pos[MaxN + 5];

int lowerbound(int num, int p) {
    int lb = 0, rb = (int)pos[num].size() - 1;
    while(lb <= rb) {
        int mid = (lb + rb) >> 1;
        if(pos[num][mid] <= p) lb = mid + 1;
        else rb = mid - 1;
    }
    return (lb < pos[num].size() ? pos[num][lb] : -1);
}
int main() {
	int T;
    scanf("%d", &T);
    while(T--) {
        vector<int> ans;
        scanf("%d", &N);
        for(int i = 0; i <= N; i++) pos[i].clear();
        for(int i = 1; i <= N; i++)
            scanf("%d", &A[i]), pos[A[i]].push_back(i);
        int lb = 0, rb = lb + 1;
        while(lb < N) {
            rb = lb + 1;
            for(int i = 0; i <= N; i++) {
                int t = lowerbound(i, lb);
                if(t == -1) {
                    ans.push_back(i);
                    break;
                }
                rb = max(rb, t);
            }
            lb = rb;
        }
        printf("%u\n", ans.size());
        for(auto i : ans) printf("%d ", i);
        puts("");
    }
	return 0;
}