ABC143F Distinct Numbers

这道题非常好。其思想类似于 $O(n \log n)$ 求最长上升子序列的算法。

hint：考虑固定操作次数 $o$，$k$ 最大可取到多少？

    int n;

    scan(n);

    vi a(n);

    scan(a);

    // appearance[i]: i 出现的次数

    vi appearance(n + 1);

    FOR (x, a) {

        appearance[x]++;

    }

    // sum[i]：出现不超过i次的数，出现的总次数

    vi sum(n + 1);

    FOR (x, appearance) {

        sum[x] += x;

    }

    rng (i, 2, n + 1) {

        sum[i] += sum[i - 1];

    }

    vi cnt(n + 1);

    FOR (x, appearance) {

        cnt[x]++;

    }

    // cnt[i]：出现次数大于等于i的数字的个数

    down (i, n - 1, 1) {

        cnt[i] += cnt[i + 1];

    }

    // max_k[i]: 固定操作次数i，k最大可取到多少

    vi max_k(n + 2);

    max_k[0] = n;

    max_k[n + 1] = 0;

    // max_k[] 单调不增，max_k[i] >= max_k[i + 1]

    rng (i, 1, n + 1) {

        max_k[i] = cnt[i] + sum[i - 1] / i;

    }

    down (i, n, 0) {

        rng (j, max_k[i + 1] + 1, max_k[i] + 1) {

            println(i);

        }

    }

巴特西

ABC143F Distinct Numbers

最新文章

热门文章