ARC080C Young Maids

发表于 更新于 分类于 ， ， 阅读次数：

题意 ： 给定 元排列 （保证 为偶数）。

根据下述步骤构造一个 元排列 。

首先，令 为空。接下来，执行下述操作直到 为空。

  • 选择 中两个相邻元素，按原顺序设它们是 。从 中移除 ，将它们按顺序接在 的前面。

求可能的形成的字典序最小的 。

，时限 。

观察我们最终拿出的对子有什么特征，不难发现，对子形成一个括号序列，且要从里到外拿取。

考虑最后一步如何操作。

尝试寻找一个最小的，能作为最外层左括号的位置，不难发现只需下标是奇数就可以了。

接着寻找一个最小的，与之配对的右括号。这需要早左括号右边，且下标为偶数。

（这两步可以用线段树或 ST 表）

确定这一对括号之后，我们将序列分为了三部分 ：

1
...A... ( ...B... ) ...C...

这三部分的对子选取顺序是互不干扰的，故按照子问题处理。

处理完成后，我们得到了配对方案，以及对子之间的先后顺序（形如外向树）

在这个外向树上用堆贪心求出最小拓扑序列即可。

复杂度 。