AcWing 1996. 打乱字母

题目传送门:https://www.acwing.com/problem/content/1998/

解题思路:先不说思路,先来舔一波万能的sort的函数和强大的STL(狗头)。

sort能对字符串排序,没错!比如string s;sort(s.begin(),s.end());这样原字符串就变成升序的字符串啦。想要降序的,加个greater不就行了吗。

同时sort还能对字符串数组严格按字典序进行排序。比如把多个string压入vector数组中,然后sort(ss.begin(),ss.end()),就得到升序的字符串数组啦。想要降序的,同样加个greater。

知道上面这些,那这道题还不手到擒来。先将字符串用sort都改成升序的,然后压入vector,再用sort,将字符串数组排成升序数组,这种情况是最小情况。先将字符串用sort都改成降序的,然后压入vector,再用sort,将字符串数组排降序数组,这种情况是最大情况。

然后对单个字符串比较,先排成降序,然后去最小情况中去找最大位置。接着排成升序,然后去最大情况中去找最小位置。(原理不用多说,自己最小的状态,去与别人最大的情况相比,自然得到最小位置,另一种情况,反之)。

最后,要注意的一点,我在查找时用的是二分upper和lower,这个两个函数返回地址减首地址后,所对应的位置是否要加一才是正确答案,下面代码注释给有一定解释。

代码如下:

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<cstring>
#include <functional>//greater的头文件

using namespace std;
#define ll long long
const int maxn = 50000 + 500;
const int inf = 1e9 + 7;
int main() {
    int t;
    vector<string>maxs;//降序字符串
    vector<string>mins;//升序字符串
    vector<string>ss;//保存原来的字符串
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        ss.push_back(s);
        sort(s.begin(),s.end());
        mins.push_back(s);
        sort(s.begin(),s.end(),greater<char>());
        maxs.push_back(s);
    }
    sort(maxs.begin(),maxs.end());
    sort(mins.begin(),mins.end());
//    for(int i=0;i<mins.size();i++)cout<<mins[i]<<' ';
//    cout<<endl;
//    for(int i=0;i<maxs.size();i++)cout<<maxs[i]<<' ';
//    cout<<endl;
    for(int i=0;i<ss.size();i++){
        sort(ss[i].begin(),ss[i].end(),greater<char>());
        string s1=ss[i];//降序字符串
        int ma=upper_bound(mins.begin(),mins.end(),s1)-mins.begin();//用自己最大的情况去和其他最小的情况相比,得到最大位置。
        // 这种情况不用加一,因为它的正确位置是在lower_bound返回位置前面的一个位置
        sort(ss[i].begin(),ss[i].end());
        string s2=ss[i];//升序字符串
        int mi=lower_bound(maxs.begin(),maxs.end(),s2)-maxs.begin()+1;//用自己最小的情况去和其他最大的情况相比,得到最小位置.
        // 这种情况要加一,因为它的正确位置就是在lower_bound返回的位置
        cout<<mi<<' '<<ma<<endl;
    }
    return 0;
}

上一篇:Java8 Optioanl解决空指针异常


下一篇:面向对象