K 题

题解

在数组 中，每个给出的 前一定有一段 的子序列，不妨把这段子序列连续地放在 前，之后判断构造出的数组 是否合法。

数组 合法即 且不存在两个相邻的数后者与前者之差大于 。

之后，考虑 的位置，因为 是最小的，每次出现一定会将栈清空且无法被之后的数清空，所以 一定在最右的 处。

接下来考虑 的位置，因为此时 是剩下未使用过的数中最小的数，所以 会在次右的 或最右的 处。

……

重复以上步骤直至将 个数放完。

即，将构造好的数组 按值从小到大，位置从右至左的顺序依次赋上 即可。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> b(n);
    vector<bool> vis(n);
    for (int i = 0; i < k; i++) {
        int p, x;
        cin >> p >> x;
        --p;
        b[p] = x;
        vis[p] = true;
    }
    for (int i = 0; i < n; i++) {
        if (vis[i]) { // 如果是给出的 b[i]
            for (int j = i - 1; j >= 0 and not vis[j]; j--) { // 将 1,2,...,b[i] - 1 连续地放在 b[i] 前
                b[j] = max(1, b[j + 1] - 1);
            }
        }
    }
    for (int i = 1; i < n; i++) { // 防止没给出 b[n - 1]，因为之前只往左放
        if (b[i] == 0) {
            b[i] = b[i - 1];
        }
    }
    bool ok = b[0] == 1; 
    for (int i = 1; i < n; i++) { // 判断构造出的数组 b 是否合法
        if (b[i] - b[i - 1] > 1) {
            ok = false;
        }
    }
    if (not ok) {
        cout << -1 << "\n";
        return 0;
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int x, int y) { // 按值从小到大，位置从右至左的顺序排序
        return b[x] != b[y] ? b[x] < b[y] : x > y;
    });
    vector<int> ans(n);
    for (int i = 0; i < n; i++) { // 依次赋上 1,2,...,n
        ans[p[i]] = i + 1;
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
    return 0;
}