2020 CCPC Wannafly Winter Camp Day6 Div.12——G.单调栈【思维、贪心思想】

题目传送门

题目描述

对于一个 $1...n$ 的排列 $p[1...n]$，我们这样定义它的单调栈 $f[1...n]$：
对于 $i$，若 $p[1...i?1]$ 中比 $p[i]$ 小的数里最大的是 $p[j]$，则 $f[i]=f[j]+1$，若不存在这样的数，则 $f[i]=1$
现在你得到了 $f$ 中某些位置的值，求一个字典序最小的 $p$ 使得它满足这些值。
数据保证一定有解：数据的生成方式为先随机生成一个 $p$，然后求出它的 $f$，再随机去掉一些位置的值。
对于两个数组 $a[1...n]$ 和 $b[1...n]$，前者的字典序比后者小，当且仅当存在某个 $j$ 使得 $a[1...j]=b[1...j]$ 且 $a[j+1]<b[j+1]$

输入描述:

第一行一个正整数 $T$ 表示数据组数
对于每组数据，第一行一个正整数 $n$，第二行 $n$ 个整数表示 $f[1...n]$，若 $f[i]=?1$ 则表示这个 $f[i]$ 不知道是什么，你不需要去关心它。
$(1\le T\le 100)$，$(1\le n\le 100)$

输出描述:

对于每组数据，输出一行 $n$ 个整数，表示字典序最小的 $p[1...n]$，注意不要有行末空格

输入

3
4
-1 2 -1 2
6
1 -1 2 -1 3 -1
4
-1 -1 1 -1

输出

1 3 4 2
1 3 2 5 4 6
2 3 1 4

题解

• 首先考虑，对于所有$f[i]$=1，说明 $p[1...i?1]$ 中没有比 $p[i]$ 小的，那么为了满足字典序最小，$p[i]$ 应该是 $1$，但是可以有很多个 $f[i]=1$，那么如果有 $k$ 个 $f[i]=1$ ，则 $p[i...k]$ 应该为 $k...1$
• 那么此时所有 $f[]=1$ 的都确定了，可以将所有 $f[]减去1$
• 现在考虑不能确定的位置：$f[i]=?1$，题意想表达的是：对于 $f[]=?1$ 的位置，不在上述确定 $f[]$ 大小的考虑范围内，也就是说，对于给定的 $f[]=?1$，它的未知，是指由 $p[]$ 确定 $f[]$ 的时候，不考虑 $f[]=?1$ 的位置。简而言之，就是 $f[]=?1$ 的位置，后面确定 $p[]$ 的时候，不考虑前面的 $f[]=?1$ 的真值。
• 搞懂题意之后，我们知道，既然 $f[]=?1$ 的位置对 $p[]$ 无影响，那么为了使字典序最小，在每次寻找 $f[]=t$的时候，第一次扫描结束之后，下一次扫描开始之前，找到第一个 $f[]=t$ 之前的 $f[]=?1$ 的位置，设置为 $cnt+1$
• 详情见代码
• 这里考虑对于 $f[]=?1$ 操作的正确性：由 $样例2$ 推算可得，但是具体正确原因还是没搞懂，如果有明白的还请评论区讲解一下~~

AC-Code

#include <bits/stdc++.h>using namespace std;const int maxn = 105;int f[maxn];
int p[maxn];int main() {
    int T;    cin >> T;while (T--) {
    int n;    cin >> n;for (int i = 1; i <= n; ++i) {
    cin >> f[i];}int t = 1;int cnt = 0; // 扫描的t只是为了确定顺序，而cnt则是确定位置之后填充的数字while (cnt < n) {
    for (int i = n; i >= 1; --i) {
     if (f[i] == t)p[i] = ++cnt;}for (int i = 1; i <= n; ++i) {
    if (f[i] == t) {
    break;}else if (f[i] == -1) {
    p[i] = ++cnt;f[i] = t;break;}}++t; // 把所有数都-1浪费时间，直接令t增加，就相当于所有数都减少了1}cout << p[1];for (int i = 2; i <= n; ++i) {
    cout << " " << p[i];}puts("");}return 0;
}