Acwing--1996. 打乱字母(二分)

78 阅读 0 评论 52 点赞

我是靠谱客的博主帅气雨，最近开发中收集的这篇文章主要介绍Acwing--1996. 打乱字母(二分)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

农夫约翰将按字典序排列的 NN 头奶牛的名字列表贴在了牛棚的门上。

每个奶牛的名字都由一个长度介于 11 到 2020 之间的由小写字母构成的唯一字符串表示。

麻烦制造者贝茜将列表中的奶牛名字重新排序打乱了列表。

此外，她还对每头奶牛的名字中的字母顺序进行了重新排列（也可能保持不变）。

给定修改过后的列表，请帮助约翰确定列表中的每个名字可能出现在原始列表中的最低和最高位置。

输入格式

第一行包含整数 NN。

接下来 NN 行，按照修改过后列表的顺序，给出了修改过后的奶牛的名字。

输出格式

共 NN 行，第 ii 行输出给定的第 ii 个字符串在原始列表中可能的最低和最高位置。

数据范围

1≤N≤500001≤N≤50000

输入样例：
4
essieb
a
xzy
elsie
输出样例：
2 3
1 1
4 4
2 3
样例解释

无论如何，字符串 “a” 必然出现在原始列表中第一个，类似的，字符串 “xzy” 必然出现在原始列表中的最后一个。

而字符串 “essieb” 和 “elsie” 都有可能位于原始列表的第 22 位或第 33 位，这取决于它们的原始字母顺序。

例如，”bessie” 和 “elsie” 分别位于 2,32,3 位，”sisbee” 和 “ilees” 分别位于 3,23,2 位。

#include<bits/stdc++.h>
using namespace std;
int n;
string s[50010],a[50010],b[50010];//s存储原字符串，a每个串里的字母从小到大排，b反之 


int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        a[i]=b[i]=s[i];
        sort(b[i].begin(),b[i].end(),greater<char>());//从大到小排列
        sort(a[i].begin(),a[i].end());//a取最小 
    }
    sort(b+1,b+n+1);
    sort(a+1,a+n+1);

    for(int i=1;i<=n;i++)
    {
        sort(s[i].begin(),s[i].end());//在b数组里二分出来第一个大于等于s[i] 的位置 
        int l=1,r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            if(b[mid]>=s[i])
            r=mid;
            else
            l=mid+1;

        }
        cout<<r<<" ";
        //从大到小排序一下这里不需要重排，直接reverse一下
        reverse(s[i].begin(),s[i].end());


        l=1,r=n;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(a[mid]<=s[i])
            l=mid;
            else
            r=mid-1;
        }
        cout<<r<<endl;

    }
    return 0;

}