B4069 [GESP202412 四级] 字符排序

chen_zhe · 2024-12-14 15:21:53 · 题解

欢迎报名洛谷网校，报名课程可以获得对应组别的知识点讲解与答疑服务，期待和大家一起进步！点击图片即可报名。

:::align{center} :::

本题考查字符串、排序和贪心。

本题的核心突破口在于小杨要求满足的条件：

假设 t_i 为字符串 t 的第 i 个字符，对于所有的 j\lt i 均有 t_j\le t_i。两个字符的大小关系与其在字母表中的顺序一致，例如 \texttt{e}\lt \texttt{g}\lt \texttt{p} \lt \texttt{s}。

这个条件要求了最后的字符串 t，所有字母应当是从小到大排列的，例如说最后的字符串一定是像 \tt{aaaabbbccd}（所有字母从小到大排列）的样子，而不是像 \tt{aaaabbbdcc} 的样子。

因此考虑将读入的每个字符串 s_1,s_2,\dots,s_n 从小到大排列，然后拼接在一起组成字符串 t。在 C++ 语言中，字符串的比较是根据字典序进行排列的，因此相对较小的字符串，例如说 \tt{aaaa} 会出现在 \tt{aabc} 这个更大的字符串前面。由此，我们就得到了尽可能让小的字母出现在字符串前面，大的字母出现在字符串后面的 t。随后，我们判断 t 的所有字母是否是从小到大排列的，即可完成本题。

参考代码（部分）：

//省略：将 s[i] 从小到大排序
for (int i = 1; i <= n; i++)
    ________; // 拼接形成新的字符串 t
bool flag = true;
for (int i = 0; i < ________; i++) {
    if (________) // 判断是否不满足条件
        flag = false;
}