菜鸡一个。

Codeforces 1530E Minimax 题解

2021-07-31 12:33:37


一道很好的构造题,锻炼思维。

以下设原串长为 $len$。

Case 1: 只有一种字符

直接输出原串即可。

Case 2: 有多种字符

Case 2.1: 存在一种字符出现次数为1

显然把这个字符放在最前面,其他字符排序后接在后面即可。

如:$\texttt{bbcaaa}$ 最优解为 $\texttt{caaabb}$。

Case 2.2: 所有字符出现次数大于等于2

不妨设最小的字符为 $\texttt{a}$,其出现次数为 $cnt$。

那么,最后的答案为 $1$。

由于要保证字典序最小,我们尽可能多地把 $\texttt{a}$ 放在最前。不难发现最前面最多有有连续两个 $\texttt{a}$。

Case 2.2.1 最前面可以放连续两个 a

考虑除这两个 $\texttt{a}$ 以外的 $\texttt{a}$,由于这些 $\texttt{a}$ 不能连续出现,所以这些 $\texttt{a}$ 每个后要么接一个非 $\texttt{a}$ 的字符,要么放在字符串尾。所以,字符串最前面可以放连续两个 $\texttt{a}$,当且仅当 $cnt-1 \le len-cnt+1$ (注意:从前往后第二个 $\texttt{a}$ 后也要接非 $\texttt{a}$ 的字符)。

可行性知道了,那还要构造最优解。显然,我们把所有非 $\texttt{a}$ 的字符排序,在相邻两个字符间依次插入 $\texttt{a}$ 直至 $\texttt{a}$ 用完。如果 $\texttt{a}$ 没有用完则一定还剩 $1$ 个 $\texttt{a}$,放在串最后即可。

例:$\texttt{baaaaaabcc}$ 最优解为 $\texttt{aababacaca}$。

Case 2.2.2 最前面不能放连续两个 a

那么,最前面只能放一个 $\texttt{a}$。

在其之后一定会接第二小的字符,不妨设为 $\texttt{b}$。

那么,后面不能再出现形如 $\texttt{ab}$ 这样的串了。

若字符种类 $\le 2$,所有的 $\texttt{a}$ 应放在所有的 $\texttt{b}$ 之后(否则一定会出现形如 $\texttt{ab}$ 这样的串)。如 $\texttt{bbabaaaaa}$ 的最优解为 $\texttt{abbbaaaaa}$。

否则,我们可以在最前面的 $\texttt{b}$ 后接所有的 $\texttt{a}$,再接一个第三小的字符(不妨设为 $\texttt{c}$ ),然后剩下的字符放置的位置没有限制,直接从小到大排序即可。如 $\texttt{bbaaaaaaaaaccdd}$ 的最优解为 $\texttt{abaaaaaaaacbcdd}$。

Code