专栏文章

B4069 [GESP202412 四级] 字符排序

cchen_zheAya
B4069题解参与者 26已保存评论 28

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
28 条
当前快照
1 份
快照标识符
@miqsd402
此快照首次捕获于
2025/12/04 09:57
3 个月前
此快照最后确认于
2025/12/04 09:57
3 个月前
查看原文
欢迎报名洛谷网校，期待和大家一起进步！
本题考查字符串、排序和贪心。
本题的核心突破口在于小杨要求满足的条件：
假设 tit_i 为字符串 tt 的第 ii 个字符，对于所有的 j<ij\lt i 均有 tj≤tit_j\le t_i。两个字符的大小关系与其在字母表中的顺序一致，例如 e<g<p<s\texttt{e}\lt \texttt{g}\lt \texttt{p} \lt \texttt{s}。
这个条件要求了最后的字符串 tt，所有字母应当是从小到大排列的，例如说最后的字符串一定是像 aaaabbbccd\tt{aaaabbbccd}（所有字母从小到大排列）的样子，而不是像 aaaabbbdcc\tt{aaaabbbdcc} 的样子。
因此考虑将读入的每个字符串 s1,s2,…,sns_1,s_2,\dots,s_n 从小到大排列，然后拼接在一起组成字符串 tt。在 C++ 语言中，字符串的比较是根据字典序进行排列的，因此相对较小的字符串，例如说 aaaa\tt{aaaa} 会出现在 aabc\tt{aabc} 这个更大的字符串前面。由此，我们就得到了尽可能让小的字母出现在字符串前面，大的字母出现在字符串后面的 tt。随后，我们判断 tt 的所有字母是否是从小到大排列的，即可完成本题。
参考代码（部分）：
CPP
//省略：将 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;
}

评论

共 28 条评论，欢迎与作者交流。

正在加载评论...