G4014 [GESP202412 四级] 字符排序 题解

知识点：字符串、排序、条件判断。

解题思路

先检查每个字符串自身是否非递减；再将字符串字典序排序，检查前串末字符不大于后串首字符。

为什么正确

若整体拼接有序，每个串内部必须有序；串间边界也必须有序。满足两类条件就保证所有字符非递减。

易错点

只排序字符串无法修复串内逆序；输出0或1，而非Yes或No。

复杂度

设总字符数L、最大长度K，时间O(L+nK log n)，空间O(L)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        vector<string>a(n);
        bool ok=true;
        for(auto &s:a) {
            cin>>s;
            if(!is_sorted(s.begin(),s.end()))ok=false;
        }
        sort(a.begin(),a.end());
        for(int i=1;i<n;i++)if(a[i-1].back()>a[i][0])ok=false;
        cout<<ok<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。