自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:16:52，当前版本为作者最后更新于2024-12-14 15:21:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

欢迎报名洛谷网校，期待和大家一起进步！

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

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

假设 $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 += s[i];
bool flag = true;
for (int i = 0; i < (int)t.length() - 1; i++) {
    if (t[i] > t[i + 1])
        flag = false;
}