题解：CF1971B Different String

· · 题解

题目

看到题目，就觉得很简单

明显的字符串题,但我们还是需要分析具体的做法哟~！

首先要判断能不能变成其他的字符串,遍历字符串,看看有多少个不同的字母,大于 2 即可输出YES

如果输出NO,就是每个字母都一样,没必要继续判断,所以continue;

如果有不同的字母,就把它变成另一个字符串,怎么变呢?

如果枚举判断的话,复杂度是 O(n^2) 有点慢(虽然也可以过)

推一个 O(nlog{n}) 的方式—排序!

把字符串排序,如果与原字符串不同就输出,相同就倒序后输出

话不多说,上代码!

#include<bits/stdc++.h>
using namespace std;
int cmp(char a,char b){
    return a>b;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string a;
        cin>>a;
        int p[30]={0};//保存每个字母出现的数量
        for(int x=0;x<a.size();x++){
            p[a[x]-'a']++;
        }
        int cnt=0;//保存共有多少个不同的字母
        for(int x=0;x<26;x++){
            if(p[x]!=0)cnt++;
        }
        if(cnt>=2)cout<<"YES"<<endl;//如果有不同的字母就输出YES
        else{//否则输出NO
            cout<<"NO"<<endl;
            continue;
        }
        string a1=a;//拷贝a
        sort(a1.begin(),a1.end());//排序
        if(a1==a){
            reverse(a1.begin(),a1.end());//倒序
            cout<<a1<<endl;
        }else cout<<a1<<endl;
    }
    return 0;
}

第一次写题解,求通过!