摘要
Title: 1996. 打乱字母
Tag: 贪心，二分
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1996. 打乱字母

题意

农夫约翰将按字典序排列的 N 头奶牛的名字列表贴在了牛棚的门上。
每个奶牛的名字都由一个长度介于 1 到 20 之间的由小写字母构成的唯一字符串表示。
麻烦制造者贝茜将列表中的奶牛名字重新排序打乱了列表。
此外，她还对每头奶牛的名字中的字母顺序进行了重新排列（也可能保持不变）。
给定修改过后的列表，请帮助约翰确定列表中的每个名字可能出现在原始列表中的最低和最高位置。

思路

• 本题考虑用贪心，每个字符串出现的最大位置是当其他字符串字典序均最小的时候，反之亦然。
• 我们可以先开一个列表$lst$，用来存储所有字符串字典序最小的值，不排序
• 再开两个列表$lst\_up$, $lst\_down$，分别存储所有字符串字典序最小和字典序最大的值，并升序排序。
• 在查找时，我们只需要查找每个字符串$s$的最小字典序在$lst\_down$中的位置即可得到可能出现的最小位置，反之亦然。
• 这里就需要用到二分
  • 介绍$Python$的库——$bisect$
    • bisect_left(lst_down, s), 对应lower_bound
    • bisect_right(lst_up, s[::-1]), 对应upper_bound

代码

'''
Author: NEFU AB-IN
Date: 2022-01-09 09:51:53
FilePath: \ACM\Acwing\1996.py
LastEditTime: 2022-01-09 11:43:36
'''
import bisect


def solve():
    n = int(input())
    lst = []
    lst_up = []
    lst_down = []
    for _ in range(n):
        s = sorted(input())
        lst.append(s)
        lst_up.append(s)
        lst_down.append(s[::-1])

    lst_up.sort()
    lst_down.sort()

    for s in lst:
        #lower_bound
        low = bisect.bisect_left(lst_down, s) + 1
        #upper_bound
        high = bisect.bisect_right(lst_up, s[::-1])
        print(low, high)


if __name__ == "__main__":
    solve()