初级网页设计招聘_云闪付小程序开发平台_网络营销的方法有哪些?_网站项目开发流程

$k$ 只有 $2n-1,2n-2$ 两种取值，如果 $k=2n-2$，即 $2(n-1)$，那么我们可以拿出 $n-1$ 个栈来放数，最后留一个栈（称其为特殊栈）来消除底部的数，容易证明这样肯定可以得到合法方案。

再看 $k=2n-1$，这样会出现 $2n-2$ 个数放完了，还有一个多出来的数，考虑这个数的归宿。

设多出来的数为 $w$，我们找到在它之后的最先出现在某个栈的底部的数 $u$，设 $u$ 所在栈为 $x$，该栈栈顶为 $v$，进行分讨。

• 若 $w$ 比 $u$ 先出现，那么我们将 $w$ 放入特殊栈，因为之后用不到 $2$ 操作。
• 否则比较 $u,v$，若 $u$ 比 $v$ 先出现，那么之后需要借用特殊栈消除 $u$，所以 $w$ 放到 $x$ 栈顶。
• 否则就是 $v<u<w$，我们将 $w$ 放入特殊栈，之后会出现 $v,u$ 依次被消除的情况，此时 $x$ 又空了，所以我们将 $x$ 设为新的特殊栈。

本题实现细节较多，简单说一下：

• 记录每个数所在栈。
• 用队列来维护当前有哪些空栈，注意某个数出栈时，该栈有空余位置后要重新入队。
• $1,2$ 操作分别写成函数，方便维护。

最后还有一个时间复杂度的问题，我们找 $u,v$ 的出现顺序时，能否暴力往后找？答案是可以的，因为只有出现所有非特殊栈放满后，才会去找，而下一次再出现这种情况的位置，一定不会和之前重合，所以最多只会循环 $m$ 次。

时间复杂度 $O(\sum m)$。