单调栈[Luogu P6198]
【题目描述】
有一个长度为$n$的排列$p_0, p_1, \cdots, p_{n-1}$，通过这个排列生成了一个长度为$n$的序列$S$，其中$S_i$表示由$p_0, p_1, \cdots, p_i$组成的递增单调栈的大小。
换一种说法，序列$S$是由如下代码生成的：
1 | stack<int> stk; |
现在给你序列$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 |
|
