博客

原题链接：

1996. 打乱字母 – AcWing题库


高质量的算法题库



https://www.acwing.com/problem/content/1998/

思路：

字符串排序＋二分。本题需要的前置知识：

sort可以直接排序字符串，按每个字符的字典序排序，sort也可以排序字符串数组，按每个字符串的字典序排序

了解了以上语法，就把这道题当成整数二分去做就行，把字符和字符串都看成整数，这题就十分清晰了。注意整数二分的两者靠拢模式，本题字典序小的应该尽量往左，大的应该尽量往右

Code：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50010;
string mmax[N],mmin[N];
string mmax_[N],mmin_[N];
int main()
{
    int n;
    cin>>n;
    int cnt=1;
    while (n -- )
    {
        string s;
        cin>>s;

        sort(s.begin(),s.end(),greater<int>());
        mmax[cnt]=s;
        mmax_[cnt]=s;

        sort(s.begin(),s.end());
        mmin[cnt]=s;
        mmin_[cnt]=s;

        cnt++;
    }

    sort(mmax+1,mmax+cnt);
    sort(mmin+1,mmin+cnt);

    for(int i=1;i<cnt;i++)
    {
        string now=mmin_[i];
        int l=1,r=cnt-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(mmax[mid]>=now) r=mid;
            else
            l=mid+1;
        }

        cout<<l<<" ";

        now=mmax_[i];
        l=1,r=cnt-1;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(mmin[mid]<=now) l=mid;
            else
            r=mid-1;
        }

        cout<<l<<endl;
    }

    return 0;
}

作者：机械之忍

链接：https://www.acwing.com/activity/content/code/content/2258833/

来源：AcWing

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。