字符排序 题解

题目分析

我们有 $n$ 个仅包含小写字母的字符串，可以将它们按任意顺序拼接成一个新字符串 $t$。要求最终的 $t$ 满足 非递减，即对于任意 $j<i$，都有 $t_j \le t_i$（按字典序比较字符）。换句话说，整个 $t$ 的字符序列必须是“从小到大”排列的。

题目要求判断是否存在一种排列顺序，使得拼接后的 $t$ 满足条件。

解题思路

首先可以发现一个重要限制：我们只能改变字符串之间的顺序，而不能改变任何一个字符串内部的字符顺序。因此，如果某个字符串内部的字符不是非降的（例如 "ba"），那么无论如何排列，该字符串内部的逆序都会被带入 $t$ 中，导致最终 $t$ 不可能整体非降。

所以我们只需考虑那些内部本身已经非降的字符串（但这道题不需要我们显式判断，因为最终检查会自然排除）。

接下来考虑整体条件：假设存在一种满足条件的排列，按该顺序拼接得到非降的 $t$。我们观察其中相邻的两个字符串 $A$ 和 $B$（$A$ 在 $B$ 前面）。由于 $t$ 整体非降，$A$ 的最后一个字符（最大值）一定小于或等于 $B$ 的第一个字符（最小值）。记 $A$ 的最大字符为 $A_{max}$，$B$ 的最小字符为 $B_{min}$，则必须有 $A_{max} \le B_{min}$。

由 $A_{max} \le B_{min}$ 可以推出一个关键结论：$A$ 在字典序上一定小于或等于 $B$（即 $A \le B$）。简单证明如下：

• $A$ 的所有字符 $\le A_{max} \le B_{min} \le B$ 的第一个字符。
• 若 $A$ 的第一个字符小于 $B$ 的第一个字符，显然 $A<B$。
• 若第一个字符相等，则由于 $A$ 的所有字符都不能超过 $B_{min}$，$A$ 中所有字符都必须等于这个字符。而 $B$ 从第一个字符开始可能有一段相同的字符，然后变大。因此 $A$ 要么是 $B$ 的前缀，要么与 $B$ 完全相等。字典序比较结果也是 $A \le B$。

因此，满足条件的排列中，字符串的顺序一定是 字典序非降 的（即排好序的）。如果存在可行的排列，那么把所有字符串按字典序从小到大排序后，得到的排列也一定是可行的（相等字符串交换顺序不影响拼接结果）。

于是我们得到了一个非常简单的判断方法：

1. 将所有字符串按 字典序升序 排序。
2. 按排序后的顺序拼接出 $t$。
3. 检查 $t$ 是否整体非降。如果是，输出 1；否则输出 0。

如果存在任何一个可行的排列，排序后的拼接一定满足条件；反之，如果排序后的拼接不满足条件，那么不可能存在任何可行排列。

算法说明

以参考代码为例，主要步骤如下：

1. 读入测试数据组数 $T$。
2. 对于每组数据：
   • 读入 $n$ 和 $n$ 个字符串。
   • 使用冒泡排序（其它排序方法也可以，如 std::sort）将字符串按字典序升序排列。
   • 将排序后的字符串依次拼接，得到完整字符串 $t$。
   • 遍历 $t$，检查每一个字符是否 $\ge$ 前一个字符。如果发现逆序，标记为不符合。
   • 输出标记结果。

需要注意的是，参考代码中字符串下标从 $1$ 开始，排序和拼接均按此范围。

时间复杂度分析

设测试数据组数为 $T$，每组字符串数量为 $n$，每个字符串长度最大为 $L = 10$。

• 排序：冒泡排序的最坏时间复杂度为 $O(n^2)$，每次比较两个字符串的字典序需要 $O(L)$ 时间，因此排序部分约为 $O(n^2 \cdot L)$。由于 $n \le 100$，这个复杂度完全可以接受。若使用 std::sort 可优化至 $O(n \log n \cdot L)$。
• 拼接与检查：拼接总长度 $\sum |s_i| \le n \times L \le 1000$，检查时遍历一次，复杂度 $O(nL)$。
• 总体复杂度约为 $O(T \cdot (n^2 L + nL))$，在题目数据范围内非常安全。

参考代码解释

下面是题目提供的 C++ 参考代码，并附详细注释。

cpp
复制
1#include<bits/stdc++.h>
2using namespace std;
3
4// 存储字符串，最多 100 个，下标从 1 开始
5string s[110];
6
7// 冒泡排序，将字符串按字典序升序排列
8void bubble_sort(string *a, int n) {
9    bool flag = true;
10    while (flag) {
11        flag = false;
12        for (int i = 1; i < n; ++i) {
13            // 如果前一个字符串大于后一个，则交换
14            if (a[i] > a[i + 1]) {
15                flag = true;
16                string t = a[i];
17                a[i] = a[i + 1];
18                a[i + 1] = t;
19            }
20        }
21    }
22}
23
24int main() {
25    int t;
26    cin >> t;
27    while (t--) {
28        int n;
29        cin >> n;
30        for (int i = 1; i <= n; i++) {
31            cin >> s[i];
32        }
33        // 1. 按字典序排序
34        bubble_sort(s, n);
35        
36        // 2. 拼接所有字符串
37        string t = "";
38        for (int i = 1; i <= n; i++) {
39            t += s[i];
40        }
41        
42        // 3. 检查 t 是否为非递减
43        int m = t.size();
44        int fl = 1; // 1 表示满足，0 表示不满足
45        for (int i = 1; i < m; i++) {
46            if (t[i] < t[i - 1]) { // 发现逆序
47                fl = 0;
48                break;
49            }
50        }
51        cout << fl << "\n";
52    }
53}

关键点解释：

• bubble_sort 通过不断比较相邻字符串并交换，最终使整个数组按字典序升序排列。
• 拼接时直接用 + 运算符将所有字符串连起来。
• 检查非递减时，一旦遇到 $t_i<t_{i-1}$ 就标记为失败并跳出循环。

这种方法充分利用了字符串比较的传递性，以及题目特性，简化了判断逻辑，非常适合在竞赛中快速实现。