令 $T={\tt KUPC}$。从后往前贪心，维护当前选上的四种字符的数量。如果当前的字符是 $T_i$，当 $i=4$ 或者 $T_{i}$ 的数量小于 $T_{i+1}$ 的数量时我们就选上当前的字符。最后我们把选择的第 $i$ 个 K、U、P、C 分成一组。正确性可以用交换论证来证明。时间复杂度 $O(N)$。
QOJ.ac
QOJ
Discussion #1533 for Problem #17724. Make Many KUPC
Type: Editorial
Status: Open
Posted by: jiangly
Posted at:
Last updated:
题解
Comments
No comments yet.