「解题报告」ARC128E K Different Values

我还是很菜啊。

先考虑判定问题。考虑先找出一些显然的必要条件。

记 \(m = \sum a_i\)。那么我们首先对 \(m\) 进行分块，每 \(k\) 个一块，设块数为 \(p\)，最后一个块的大小为 \(q\)。

首先显然需要满足每个块内的数互不相同，这意味着 \(a_i \le p\)。

其次对于 \(a_i = p\) 的 \(i\) 的数量不超过 \(q\)。

然后发现这两个条件实际上也是充分条件。证明考虑首先先把 \(a_i = p\) 的全放到块里，然后对于每个 \(i\) 按顺序放进每个块内。块内从后往前放，容易发现这样一定满足条件。

那么我们考虑字典序最小。有一个很直接的贪心：

1. 首先看当前 \(a_i=p\) 的个数有多少。假如个数等于 \(q\)，那么就填可以填的最小的满足 \(a_i = p\) 的 \(i\)；若没有，则无解。
2. 假如个数小于 \(q\)，那么就填最小的满足 \(a_i > 0\) 的 \(i\)；若没有，则无解。

这样贪心得到的显然是字典序最小的答案。考虑如何证明正确性。

我们假设在位置 \(i\) 的地方找不到合法的可放的数，但这种情况有解，那么：

1. 假如 \(a_i=p\) 的个数等于 \(q\)，那么也就是前 \(k-1\) 个数中出现了所有的 \(a_i=p\) 的 \(i\)，说明 \(q \le k-1\)。那么此时，如果删去最后 \(k-1\) 个数，此时的 \(p, q, a_i\) 均会加 \(1\)，而满足 \(a_i=p\) 的数不变，说明 \(q\) 不变，矛盾。
2. 假如 \(a_i=p\) 的个数小于 \(q\)，那么说明此时 \(a_i > 0\) 的个数小于等于 \(k-1\)。那么说明后面的空位一定小于 \(k\)，否则这种情况应当无解。那这说明 \(p=1\)，而这时候一定有所有的 \(a_i = p\)，那么这与 \(a_i=p\) 的个数小于 \(q\) 矛盾。

因此直接按照上面的策略贪心即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505, MAXM = 200005;
int n, k, m, a[MAXN];
int ans[MAXM];
bool vis[MAXN];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        m += a[i];
    }
    bool flag = true;
    for (int i = 1; i <= m; i++) {
        int q = (m - i) % k + 1, p = (m - i) / k + 1;
        int cnt = 0, fst = 0;
        for (int j = 1; j <= n; j++) if (a[j] == p) {
            if (!fst && !vis[j]) fst = j;
            cnt++;
        }
        if (cnt != q) {
            fst = 0;
            for (int j = 1; j <= n; j++) if (a[j] && !vis[j]) {
                fst = j;
                break;
            }
        }
        if (fst) {
            ans[i] = fst;
            a[fst]--;
        } else {
            flag = false;
            break;
        }
        vis[ans[i]] = 1;
        if (i >= k) vis[ans[i - k + 1]] = 0;
    }
    if (flag) {
        for (int i = 1; i <= m; i++) {
            printf("%d ", ans[i]);
        }
    } else {
        printf("-1\n");
    }
    return 0;
}