打乱字母

题目

链接：1996. 打乱字母 - AcWing题库

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

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

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

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

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

输入格式

第一行包含整数 N。

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

输出格式

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

代码

import java.util.*;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        String[] s = new String[50010];
        String[] a = new String[50010];
        String[] b = new String[50010];
        for(int i = 1; i <= n; i ++)
        {
            s[i] = in.next();
            char[] q = s[i].toCharArray();
            Arrays.sort(q);
            a[i] = String.valueOf(q);
            StringBuilder t = new StringBuilder(a[i]).reverse();
            b[i] = String.valueOf(t);
        }
        in.close();
        Arrays.sort(a, 1, n + 1);
        Arrays.sort(b, 1, n + 1);
        for(int i = 1; i <= n; i ++)
        {
            char[] tt = s[i].toCharArray();
            Arrays.sort(tt);
            String t = String.valueOf(tt);
            int l = 1, r = n;
            while(l < r)
            {
                int mid = (l + r) >> 1;
                if(b[mid].compareTo(t) >= 0)
                    r = mid;
                else
                    l = mid + 1;
            }
            System.out.print(l + " ");
            t = String.valueOf(new StringBuilder(t).reverse());
            l = 1;
            r = n + 1;
            while(l < r)
            {
                int mid = (l + r) >> 1;
                if(a[mid].compareTo(t) > 0)
                    r = mid;
                else
                    l = mid + 1;
            }
            System.out.println(l - 1);

        }
    }
}
/*
4
essieb
a
xzy
elsie
 */