训练营2-题K

题目大意

数组a为从1到n的n个数的排列，数组b由以下操作得到：

Stk is an empty stack
for i = 1 to n :
    while ( Stk is not empty ) and ( Stk's top > a[i] ) : 
        pop Stk
    push a[i]
    b[i]=Stk's size

现给出b中的k个数，求符合条件的a序列并输出

如果没有合法的a序列，则输出-1

题目分析

（答案不唯一，现考虑其中一种可能状况）

首先考虑b的完整序列如何构造

​ 数组b前由一段1，2， ···bi - 1的子序列，把这段序列连续的放在bi前

 for (int i = 0; i < n; i++) {
        if (vis[i]) {
            for (int j = i - 1; j >= 0 and not vis[j]; j--) {
                b[j] = max(1, b[j + 1] - 1);
            }
        }
    }

​ 再判断b是否合法，即看b0 = 1和不存在相邻两数后者与前者之差大于一是否成立

 for (int i = 1; i < n; i++) { // 判断构造出的数组 b 是否合法
        if (b[i] - b[i - 1] > 1) {
            ok = false;
        }
    }

再考虑如何由b推a

​ 在这种情况下，越小的值越尽可能靠右

vector<int> p(n);//创建一个指定长度为n的一维vector
    iota(p.begin(), p.end(), 0);//创建一个指定长度为n的一维vector
    sort(p.begin(), p.end(), [&](int x, int y) { //[&]：以引用形式捕获所有外部变量，也就是外部变量均可用
        return b[x] != b[y] ? b[x] < b[y] : x > y;
        });

最后将a依次赋值

 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];
    }

完整代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    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]) {
            for (int j = i - 1; j >= 0 and vis[j] == 0; j--) {
                b[j] = max(1, b[j + 1] - 1);
            }
        }
    }
    for (int i = 1; i < n; i++) {
        if (b[i] == 0) {
            b[i] = b[i - 1];
        }
    }
    bool ok = b[0] == 1; 
    for (int i = 1; i < n; i++) {
        if (b[i] - b[i - 1] > 1) {
            ok = false;
        }
    }
    if (ok == 0) {
        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++) {
        ans[p[i]] = i + 1;
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
    return 0;
}
注：本题解参考了
https://blog.nowcoder.net/n/1a8897ea58004f15a93d0ee7009ac99a