grant's Blog

记录生活中的点点滴滴

2022寒假每日一题笔记（一）

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 12k 阅读时长 ≈ 10 分钟

第一周

2022.1.3—2058. 笨拙的手指

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
奶牛贝茜正在学习如何在不同进制之间转换数字。
但是她总是犯错误，因为她无法轻易的用两个前蹄握住笔。
每当贝茜将数字转换为一个新的进制并写下结果时，她总是将其中的某一位数字写错。
例如，如果她将数字 14 转换为二进制数，那么正确的结果应为 1110，但她可能会写下 0110 或 1111。
贝茜不会额外添加或删除数字，但是可能会由于写错数字的原因，写下包含前导 0 的数字。
给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果，请确定 N 的正确初始值（十进制表示）。

输入格式
第一行包含 N 的二进制表示，其中一位是错误的。
第二行包含 N 的三进制表示，其中一位是错误的。

输出格式
输出正确的 N 的值。

数据范围
N 一定不超过 10^9，且存在唯一解。

输入样例：
1010
212
输出样例：
14
样例解释
14 在二进制下的正确表示为 1110，在三进制下的正确表示为 112。

大概思路是枚举二进制和三进制的错误位，然后拼出一个十进制结果。

假设a表示 N 的错一位二进制表示，b表示 N 的错一位三进制表示。

在数据范围内的二进制数的位数大概是30位，所以和a错一位的二进制数也就30个左右。爆搜这些数然后转十进制，计算量大概30*30 = 900，然后和三进制类似的计算结果比较，两个转换后的十进制数相等就找到了答案。

转换后的数可以用哈希表来存储，发现重复数就找到了答案。

显然满足时间限制。

新知识点：其他进制转十进制的秦九韶算法。

秦九韶算法，秦九韶提出的一种多项式简化算法。

一般地，一元n次多项式的求值需要经过(n+1)*n/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法，降低了时间复杂度。（ O(n^2) —> O(n) ）

img

其他进制转十进制的过程，也就是按权展开，其实是求一个多项式的值，利用秦九韶算法提高效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;

int get(string s,int b){
    // 秦九韶算法：b进制转换为十进制
    int res = 0;
    for (auto &c : s) // s[0]存的是二进制数的高位
        res = res*b + c - '0';
    return res;
}

int main(){
    string a,b;
    unordered_set<int> set; // 哈希表
    
    cin >> a >> b;
    
    for (auto &c : a){ // 取引用修改c的值
        c ^= 1; // '0'的ASCII码是48，异或之后就是49，也就是'1'
        set.insert(get(a,2));
        c ^= 1; // 恢复状态
    }
    
    for (auto &c : b){
        char t = c;
        for (int i = 0;i < 3;i ++){ // 三进制每一位有0,1,2三种情况
            if (i + '0' != t){
                c = i + '0';
                int x = get(b,3);
                if (set.count(x)){ // 重复出现的就是答案
                    cout << x;
                    return 0;
                }
            }
        }
        c = t; // 恢复状态
    }
    return 0;
}

2022.1.4—2041. 干草堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
贝茜对她最近在农场周围造成的一切恶作剧感到抱歉，她同意帮助农夫约翰把一批新到的干草捆堆起来。
开始时，共有 N 个空干草堆，编号 1∼N。
约翰给贝茜下达了 K 个指令，每条指令的格式为 A B，这意味着贝茜要在 A..B 范围内的每个干草堆的顶部添加一个新的干草捆。
例如，如果贝茜收到指令 10 13，则她应在干草堆 10,11,12,13 中各添加一个干草捆。
在贝茜完成了所有指令后，约翰想知道 N 个干草堆的中值高度——也就是说，如果干草堆按照高度从小到大排列，位于中间的干草堆的高度。
方便起见，N 一定是奇数，所以中间堆是唯一的。
请帮助贝茜确定约翰问题的答案。

输入格式
第一行包含 N 和 K。
接下来 K 行，每行包含两个整数 A,B，用来描述一个指令。

输出格式
输出完成所有指令后，N 个干草堆的中值高度。

数据范围
1≤N≤10^6,
1≤K≤25000,
1≤A≤B≤N
输入样例：
7 4
5 5
2 4
4 6
3 5
输出样例：
1
样例解释
贝茜完成所有指令后，各堆高度为 0,1,2,3,3,1,0。
将各高度从小到大排序后，得到 0,0,1,1,2,3,3，位于中间的是 1。

算法思路：差分再排序。

排序可以直接sort，也可以利用nth_element（库函数，原理是快排求第k个数，参考基础课）。

快排求第k个数，acwing.786.第k个数，时间复杂度：O(n)，每次查找数据减少一半。

本题挺水的，是基础课的练习题，复习一下差分数组和快排。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+5; // 数据量 >= 1e6 建议scanf
int h[N];

void add(int l,int r){ // 一维差分
    h[l] += 1;
    h[r+1] -= 1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n,k;
    cin >> n >> k;
    
    int a,b;
    while (k--){
        cin >> a >> b;
        add(a,b);
    }
    
    for (int i = 1;i <= n;i ++){
        h[i] += h[i-1]; // 求前缀和得到真正的数组
    }
    
    sort(h+1,h+n+1);
    // nth_element(h+1,h+(n+1)/2,h+n+1); 库函数，
    
    cout << h[(n+1)/2]; // 求中位数
    return 0;
}

2022.1.5—2060. 奶牛选美

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。
不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。
牛皮可用一个 N×M 的字符矩阵来表示，如下所示：
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
其中，X 表示斑点部分。
如果两个 X 在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。

约翰牛群里所有的牛都有两个斑点。
约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。
在上面的例子中，他只需要给三个 . 区域内涂色即可（新涂色区域用 ∗ 表示）：
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....
请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。

输入格式
第一行包含两个整数 N 和 M。
接下来 N 行，每行包含一个长度为 M 的由 X 和 . 构成的字符串，用来表示描述牛皮图案的字符矩阵。

输出格式
输出需要涂色区域的最少数量。

数据范围
1≤N,M≤50
输入样例：
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
输出样例：
3

没有思路。

题目解读：用最少的字符连通两个连通块。

复习一下搜索连通块的算法：Flood Fill算法。（用BFS或DFS实现，BFS可以求最短路，DFS不行）

参考蓝桥杯学习总结（十九）中的红与黑。

本题需要存连通块中所有点的坐标，算是对蓝桥杯题型的补充。

y总讲解：

image-20220105165358764

对于两个连通块中的任意两点，不能直接套用公式求两点的最少连通字符数量，因为路径上可能存在障碍。

一个有障碍的路径肯定不是最优解，最优解的两点一定满足公式。

时间复杂度：O(n*m)，n，m分别是两个连通块中点的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> PII;
const int N = 55;
char g[N][N];
vector<PII> points[2];
int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};
int n,m;

void dfs(int x,int y,vector<PII> &p){
    g[x][y] = '.';
    p.push_back({x,y});
    
    for (int i = 0;i < 4;i ++){
        int a = x+dx[i],b = y+dy[i];
        if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'X')
            dfs(a,b,p);
    }
}

int main(){
    cin >> n >> m;
    
    for (int i = 0;i < n;i ++) cin >> g[i];
            
    for (int i = 0,k = 0;i < n;i ++)
        for (int j = 0;j < m;j ++)
            if (g[i][j] == 'X')
                dfs(i,j,points[k++]);
                
    int res = 1e9;
    for (auto &a : points[0])
        for (auto &b : points[1])
            res = min(res,abs(a.fi-b.fi)+abs(a.se-b.se) - 1); // 距离记得-1
            
    cout << res << '\n';
    return 0;
}

2022.1.6—2019. 拖拉机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
干了一整天的活，农夫约翰完全忘记了他把拖拉机落在田地中央了。
他的奶牛非常调皮，决定对约翰来场恶作剧。
她们在田地的不同地方放了 N 捆干草，这样一来，约翰想要开走拖拉机就必须先移除一些干草捆。
拖拉机的位置以及 N 捆干草的位置都是二维平面上的整数坐标点。
拖拉机的初始位置上没有干草捆。
当约翰驾驶拖拉机时，他只能沿平行于坐标轴的方向（北，南，东和西）移动拖拉机，并且拖拉机必须每次移动整数距离。
例如，驾驶拖拉机先向北移动 2 单位长度，然后向东移动 3 单位长度。
拖拉机无法移动到干草捆占据的位置。
请帮助约翰确定他需要移除的干草捆的最小数量，以便他能够将拖拉机开到二维平面的原点。

输入格式
第一行包含三个整数：N 以及拖拉机的初始位置 (x,y)。
接下来 N 行，每行包含一个干草捆的位置坐标 (x,y)。

输出格式
输出约翰需要移除的干草捆的最小数量。

数据范围
1≤N≤50000,
1≤x,y≤1000
输入样例：
7 6 3
6 2
5 2
4 3
2 1
7 3
5 4
6 4
输出样例：
1

本题难度增加。

图论问题：首先将具体问题建图。

image-20220107205358819

将问题提炼出来，就是求起点到终点的最短路，边权分为0和1两种。

BFS只能求解边权都相同的最短路。

求解本问题需要用到提高课的双端队列广搜。

双端队列BFS，本质上是简化版本的堆优化Dijkstra算法（忘了就复习一下），用双端队列替换其中的堆。

双端队列注意点：

1.边权为0放队首 为1放队尾

2.只有被更新的点才有资格放入队列（因为不被更新说明已经放入进去了，已经被更新过了，且这次不需要更新）

3.第一次出列的是最短点 会有冗余（多次被更新） 但是此题不需要处理 只需要(0,0)一出列就返回即可

双端BFS具有两段性，双端队列中的点最多分为两段，两段中的点到原点的距离相差1。

用数学归纳法证明如下：n是指队列长度（点的个数）

image-20220107211009109

当双端队列只有一段时，结论易证。

地图的大小有限制，1≤x,y≤1000，注意搜索的路径可以在地图外面，容易发现最多只要走地图外一圈。

和堆优化Dijkstra类似，需要在出队时判重，不要入队判重！判重是为了保证运行效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
#include <cstring>
#include <deque>
using namespace std;
typedef pair<int,int> PII;
#define fi first
#define se second
const int N = 1010;
int dist[N][N];
bool st[N][N],g[N][N];
int n,x,y;
int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};

int bfs(int sx,int sy){ // 双端队列广搜
    deque<PII> q;
    q.push_back({sx,sy});
    memset(dist,0x3f,sizeof dist);
    dist[sx][sy] = 0; // 搜索一条从sx,sy走到0,0的带权最短路
    
    while (q.size()){
        auto t = q.front();
        q.pop_front();
        
        int x = t.fi,y = t.se;
        if (st[x][y]) continue; // 出队判重优化
        st[x][y] = true;
        
        if (!x && !y) break; // 0,0第一次出现的时候是最短路
        
        for (int i = 0;i < 4;i ++){
            int a = x+dx[i],b = y+dy[i];
            if (a >= 0 && a <= 1001 && b >= 0 && b <= 1001){
                int w = 0;
                if (g[a][b]) w = 1; // 有干草堆则边权为1，否则为0
                if (dist[a][b] > dist[x][y] + w){
                    dist[a][b] = dist[x][y] + w;
                    if (!w) q.push_front({a,b}); // w为0加入队头
                    else q.push_back({a,b}); // 否则加入队尾
                }
            }
        }
    }
    return dist[0][0];
}

int main(){
    cin >> n >> x >> y;
    
    int a,b;
    while (n--){
        cin >> a >> b;
        g[a][b] = true; // 有干草堆则为true
    }
    
    cout << bfs(x,y) << '\n';
    return 0;
}

SPFA也能做，参考：https://www.acwing.com/solution/content/81838/。

其他最短路算法应该也能处理。

2022.1.7—2014. 岛

每当下雨时，农夫约翰的田地总是被洪水淹没。

由于田地不是完全水平的，所以一些地方充满水后，留下了许多被水隔开的“岛”。

约翰的田地被描述为由 N 个连续高度值 H1,…,HN 指定的一维场景。

假设该场景被无限高的围墙包围着，请考虑暴雨期间发生的情况：

最低处首先被水覆盖，形成一些不连贯的岛，随着水位的不断上升，这些岛最终都会被覆盖。

一旦水位等于一块田地的高度，那块田地就被认为位于水下。

fig_islands.png

上图显示了一个示例：在左图中，我们只加入了刚好超过 11 单位的水，此时剩下 44 个岛（最大岛屿剩余数量），而在右图中，我们共加入了 77 单位的水，此时仅剩下 22 个岛。

请计算，暴风雨期间我们能在某个时间点看到的最大岛屿数量。

水会一直上升到所有田地都在水下。

输入格式

第一行包含整数 N。

接下来 N 行，每行包含一个整数表示 Hi。

输出格式

输出暴风雨期间我们能在某个时间点看到的最大岛屿数量。

数据范围

1≤N≤10^5,

1≤Hi≤10^9

1
2
3
4
5
6
7
8
9
10
11
12
输入样例：
8
3
5
2
3
1
4
2
3
输出样例：
4

题目不太能读懂。

思路：

image-20220108162459395

但是存在一些特殊情况需要考虑，如果是下图这种情况，中间有连续一段相等高度的田，只考虑最右边三块田就是错误的。

image-20220108162535736

解决方案：将中间连续一段相等高度的田合并为一块田，使用unique函数去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
typedef pair<int,int> PII;
#define fi first
#define se second
int n,h[N];
PII q[N];

int main(){
    cin >> n;
    
    for (int i = 1;i <= n;i ++) cin >> h[i];
    
    n = unique(h+1,h+n+1) - (h+1); // 去重，除去相邻的高度相等的一段田
    h[n+1] = 0; // 也默认了h[0] = 0，这两个高度在判断时都会用到
    for (int i = 1;i <= n;i ++) q[i] = {h[i],i};
    sort(q+1,q+n+1); // 对高度排序
    
    int res = 1,cnt = 1;
    for (int i = 1;i <= n;i ++){
        int y = q[i].se;
        
        if (h[y-1] > h[y] && h[y+1] > h[y]) cnt ++; // 两边高中间低
        else if (h[y-1] < h[y] && h[y+1] < h[y]) cnt --; // 中间高两边低
        // 两个非连续的高度相等的田需要同时更新res
        if (q[i].fi != q[i+1].fi) res = max(res,cnt);
    }
    
    cout << res;
    return 0;
}

还有细节需要考虑：如果有两个非连续的高度相等（都是h）的田，当考虑水面上升到h时，不能只考虑第一块田然后计算cnt并更新res，必须同时考虑两块田然后计算cnt，直到计算两次cnt后才更新res。

考虑一组数据：7 ,2,1,2,1,2,1,2， 答案是4。

2022.1.8—2005. 马蹄铁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
尽管奶牛贝茜发现每个平衡括号字符串都很美观，但她特别喜欢被她称为“完全”平衡的括号字符串----一个由 ( 构成的字符串后接一个长度相同的 ) 构成的字符串。
例如：
(((())))
有一天，当贝茜穿过牛棚时，她发现地面上有一个 N×N 的马蹄铁矩阵。每个马蹄铁的方向都看上去像 ( 或 )。
从矩阵的左上角开始，贝茜希望四处走动以拾起马蹄铁，使得她捡起的马蹄铁按顺序构成的括号字符串是完全平衡的。
请计算她能得到的最长完全平衡括号字符串的长度。
每一步中，贝茜可以沿上下左右四个方向移动。
她只能移动到包含马蹄铁的方格区域内，当她进入该区域时就会拿起那里的马蹄铁，并无法再次回到该位置（因为该位置没有马蹄铁了）。
她首先拿起的是左上角的马蹄铁。
由于她拿起的马蹄铁要形成一个完全平衡的字符串，因此她可能无法将所有马蹄铁都拿起来。

输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个长度为 N 的括号字符串，用来表示括号矩阵。

输出格式
输出她能得到的最长完全平衡括号字符串的长度。
如果无法得到完全平衡括号字符串（例如，左上角马蹄铁形如 )），则输出 0。

数据范围
2≤N≤5
输入样例：
4
(())
()((
(()(
))))
输出样例：
8
样例解释
贝茜的移动步骤如下：
1())
2)((
345(
876)

画出DFS搜索状态机：

image-20220108173418918

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;
int n,ans;
bool st[10][10];
char g[10][10];
int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};

void dfs(int x,int y,int l,int r){
    st[x][y] = true;
    
    if (l == r){
        ans = max(ans,l+r);
        st[x][y] = false; // 回溯前先将st复原
        return;
    }
    
    for (int i = 0;i < 4;i ++){
        int a = x + dx[i],b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < n && !st[a][b]){
            if (g[x][y] ==')' && g[a][b] == '(') continue; // 排除不合法搜索状态
            if (g[a][b] == '(') dfs(a,b,l+1,r);
            else dfs(a,b,l,r+1);
        }
    }
    
    st[x][y] = false; // 回溯前先将st复原
}

int main(){
    cin >> n;
    
    for (int i = 0;i < n;i ++)
        for (int j = 0;j < n;j ++)
            cin >> g[i][j];
    
    if (g[0][0] == '(') dfs(0,0,1,0);
    
    cout << ans;
    return 0;
}

2022.1.9—1996. 打乱字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
农夫约翰将按字典序排列的 N 头奶牛的名字列表贴在了牛棚的门上。
每个奶牛的名字都由一个长度介于 1 到 20 之间的由小写字母构成的唯一字符串表示。
麻烦制造者贝茜将列表中的奶牛名字重新排序打乱了列表。
此外，她还对每头奶牛的名字中的字母顺序进行了重新排列（也可能保持不变）。
给定修改过后的列表，请帮助约翰确定列表中的每个名字可能出现在原始列表中的最低和最高位置。

输入格式
第一行包含整数 N。
接下来 N 行，按照修改过后列表的顺序，给出了修改过后的奶牛的名字。

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

数据范围
1≤N≤50000
输入样例：
4
essieb
a
xzy
elsie
输出样例：
2 3
1 1
4 4
2 3
样例解释
无论如何，字符串 “a” 必然出现在原始列表中第一个，类似的，字符串 “xzy” 必然出现在原始列表中的最后一个。
而字符串 “essieb” 和 “elsie” 都有可能位于原始列表的第 2 位或第 3 位，这取决于它们的原始字母顺序。
例如，”bessie” 和 “elsie” 分别位于 2,3 位，”sisbee” 和 “ilees” 分别位于 3,2 位。

思路：

求出每个字符串的最小字典序字母和最大字典序字母。

然后求字符串 x 的最低位置和最高位置。

最低位置就是 x 取最小字母，其他字符串都取最大字母的排名；

最高位置就是 x 取最大字母，其他字符串都取最小字母的排名。

时间复杂度估算：根据题目数据范围，应当控制在O(n*log n)左右。

为什么想到二分？

计算最低位置和最高位置，如果每次生成一个序列再排序就很麻烦而且必定超时。

我们发现每次计算时只需要变动一个数就行。

所以这样处理：

全部字符串取最大字母排序，然后删掉x的最大字母，二分查找 x 的最小字母，这样计算最低位置。

其实 x 的最大字母可以不用删掉，因为它一定不会影响 x 的最小字母的排名。

计算最高位置同理。但是这里必须删掉 x 的最小字母。

本题还用到了对于字符串string的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;
int n;
string a[N],_max[N],_min[N];

int main(){
    cin >> n;
    
    for (int i = 1;i <= n;i ++){
        cin >> a[i]; // a[]是原始字符串序列
        _max[i] = _min[i] = a[i]; // _max[]和_min[]是按字典序大到小、小到大的字符串序列
        
        sort(_max[i].begin(),_max[i].end(),greater<>());
        sort(_min[i].begin(),_min[i].end());
    }
    
    sort(_max + 1,_max + n + 1); // 取最大字母从小到大排序
    sort(_min + 1,_min + n + 1); // 取最小字母从小到大排序
    
    for (int i = 1;i <= n;i ++){
        sort(a[i].begin(),a[i].end()); // 取a[i]最小字母
        
        int l = 1,r = n;
        while (l < r){ // 二分查找a[i]最小字母出现的下界
            int mid = l+r>>1;
            if (_max[mid] < a[i]) l = mid + 1;
            else r = mid;
        }
        cout << l << ' ';
        
        reverse(a[i].begin(),a[i].end()); // 取a[i]最小字母，这里reverse比sort更快
        l = 1,r = n;
        while (l < r){ // 二分查找a[i]最大字母出现的上界
            int mid = l+r+1>>1;
            if (_min[mid] > a[i]) r = mid - 1;
            else l = mid;
        }
        cout << l << '\n';
    }
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！