【题目描述】
有一个长度为$n$的排列$p_0, p_1, \cdots, p_{n-1}$,通过这个排列生成了一个长度为$n$的序列$S$,其中$S_i$表示由$p_0, p_1, \cdots, p_i$组成的递增单调栈的大小。

换一种说法,序列$S$是由如下代码生成的:

1
2
3
4
5
6
7
8
stack<int> stk;
int n = p.size();
vector<int> S;
for (int i = 0; i < n; i++) {
while (!stk.empty() && p[i] <= p[stk.top()]) stk.pop();
stk.push(i);
S.push_back((int)stk.size());
}

现在给你序列$S$的一部分,没有给出的部分可以取任意值。请你根据给出的$S$复原出排列$p$。如果有多种可能,输出字典序最小的。保证一定有解。

【输入格式】
第一行一个整数$n$。表示排列的长度。

接下来一行$n$个整数,表示序列$S$。其中部分项为$-1$,表示可以取任意值。

【输出格式】
一行$n$个整数,一个排列。

没有打洛谷月赛。。。但是此题似乎很可做 于是就花了半个多小时切掉了

题解

这题整体是一个贪心+递推的思路

假设我们已经确定了 由$S_1\sim S_{i-1}$推出的 字典序最小的 由$1\sim i-1$构成的排列$p$,以及$p$当前的递增单调栈$stk$注意这里的栈里存的是元素的值而不是下标

那么考虑一下怎么在$p$中插入$i$这个元素使得字典序最小

但是插入$i$这个操作我们并不好处理

不妨这样考虑 将原来$p$中所有$\ge x$的元素全部+1 然后在$p$的末尾加上一个$x$容易证明这样得到的$p$序列对应的$S_1\sim S_{i-1}$仍与原来一样

那么$x$要满足什么条件才能使得$S_i$恰好为要求的值呢 考虑一下$i-1$的递增单调栈$stk$必须要有$stk[S_i-1]<x\le stk[S_i]$这样$stk[S_i]\sim stk[top]$都会被弹出

为了使字典序最小 显然我们这里就让$x=stk[S_i]$于是我们就得到了转移

所以算法流程如下:

已知:字典序最小的 由$1\sim i-1$构成的 满足$S_1\sim S_{i-1}$要求的排列$p$以及$p$当前的递增单调栈$stk$大小为$top$

取$x=stk[S_i]$将当前$p$中所有$\ge x$的元素+1 然后将$x$放到$p$的末尾 更新单调栈

$S_i=-1$或者$S_i>top$的时候直接把$i$扔到$p$的末尾就可以了

但是大家应该都发现了 这个是$O(n^2)$的

无非就是 将所有$\ge x$的元素+1 这一步耗费了太多时间 怎么$O(1)$或$O(\log n)$解决呢?

不用什么数据结构 这里有一个奇技♂淫巧

1.如果我们要把$i$放到$p$的末尾 我们不放$i$我们放一个$i*1000005$(或者乘上任意一个大于$n$的数)

2.如果我们要令$x=stk[S_i]$然后将当前$p$中所有$\ge x$的元素+1 我们不用去一个个+1 只需要让$x=stk[S_i]-1$然后放到末尾就完事了

最后把这么做得到的答案排个序离散化一下就得到正确答案了 就算极限情况下 符合条件的$p$是一个$n\sim 1$的倒序排列 由于我们乘的数大于$n$也不会出错

时间复杂度$O(n\log n)$不知道有没有$O(n)$做法 但是由于代码中带$\log$的只有一个sort 所以跑过$1e6$还是毫无压力的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return x * f;
}

int n, a[1000005], top;
ll stk[1000005], ans[1000005], srt[1000005], mx;

int main() {
n = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
}
for (ll i = 1; i <= n; i++) {
if (a[i] == -1) {
ans[i] = i * 1000005;
stk[++top] = ans[i];
} else {
if (a[i] > top) {
ans[i] = i * 1000005;
stk[++top] = ans[i];
} else {
ans[i] = stk[a[i]] - 1;
stk[top = a[i]] = ans[i];
}
}
}
for (int i = 1; i <= n; i++) srt[i] = ans[i];
sort(srt + 1, srt + n + 1);
for (int i = 1; i <= n; i++) ans[i] = lower_bound(srt + 1, srt + n + 1, ans[i]) - srt;
for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
return 0;
}

评论