Codeforces 1530E Minimax 题解

一道很好的构造题，锻炼思维。 以下设原串长为 $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](https://codeforces.com/contest/1530/submission/122937065)