↓Skip to main content
  1. Posts/

AtCoder-ABC272E Add and Mex

·1 min·
Table of Contents

AtCoder-ABC272E Add and Mex #

题目大意 #

给定数组 $a_1, …, a_n$ , 进行如下操作 $m$ 次:

  • 对 $1\leq i\leq n$ , $a_i$ 加上 $i$

每次操作后, 输出 $mex(a)$ , 即没有在 $a$ 中出现的最小非负整数.

Solution 1 #

对于长度为 $n$ 的数组 $a$ , $0\leq mex(a)\leq n$ . 对于 $a_i$ , 只有当 $0\leq a_i + i\times j\leq n - 1$ 时才可能对结果产生影响. 因此, 我们遍历 $i$ , 只记录可能的 $j$ , 最后进行统计即可. 总复杂度为 $\sum_{i = 1}^{n} \frac{n}{i} = O(nlogn)$ .

代码如下:

#include "bits/stdc++.h"

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    map<int, set<int>> book;
    for (int i = 1; i <= n; i++) {
        for (int j = max(1, -a[i] / i); j <= min(m, (n - 1 - a[i]) / i); j++) {
            book[j].insert(a[i] + i * j);
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 0; i <= n; i++) {
            if (!book[j].count(i)) {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}