解题思路

题目给了 N 个小写字母，要我们把它们按字典序排好，再一个接一个连成一个字符串。

“字典序”就是字母在字典里的顺序：a 最小，z 最大。

做法：

1. 把 N 个字母读进数组；
2. 用 sort 排序，字符（char）默认就是按字典序排的，从 a 到 z；
3. 遍历排好序的数组，把每个字母累加到一个字符串里，输出。

用样例验证：c、d、a、c 四个字母排序后是 a、c、c、d，连起来就是 accd，和样例一致。

参考代码

// P4557 字母组合：把N个小写字母排序后连成字符串
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<char> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];  // 读入N个小写字母
    sort(v.begin(), v.end());                  // 按字典序排序
    string ans;
    for (int i = 0; i < n; i++) ans += v[i];   // 拼成字符串
    cout << ans << endl;
    return 0;
}

复杂度分析

• 排序 N 个字母是 O(N log N)，N<100，非常快。
• 总时间复杂度 O(N log N)，空间复杂度 O(N)。