摘要
Title: 1927. 自动补全
Tag: Trie、二分
Memory Limit: 64 MB
Time Limit: 1000 ms

1927. 自动补全

题意

奶牛贝茜买了一个新手机，并十分喜欢用它发短信。
但是它的大蹄子在手机的小屏幕上打字时遇到了麻烦，它总是把单词拼错。
农夫约翰同意通过编写一个自动补全程序来帮助它，当它输入部分单词时，该应用程序可以给出补全建议。
自动补全程序可以访问一个包含 W 个单词的词典，每个单词由 a…z 范围内的小写字母组成，其中所有单词中的字母总数最多为 1000000。
现在给定一个包含 N 个部分单词的列表，每个部分单词最多包含 1000 个字母。
对于每个部分单词 i，还会提供一个整数 Ki，自动补全程序需要找到词典中以部分单词 i 作为前缀的所有单词中，按字典序排序排在第 Ki 个的单词。
也就是说，对所有部分单词 i 的有效补全按字典序进行排序，输出此顺序下的第 Ki 个补全。
思路
- 二分做法
  
  将所有单词进行排序，二分查找即可，查找的结果进行判断，是否拥有此前缀，是否未出界

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-05-22 22:47:23
* @FilePath: \ACM\Acwing\1927.cpp
* @LastEditTime: 2022-05-22 23:05:28
*/
#include <bits/stdc++.h>
using namespace std;
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
#define x first
#define y second

typedef pair<string, int> PSI;

const int N = 1e6 + 10;

signed main()
{
    IOS;
    int w, n;
    cin >> w >> n;
    vector<PSI> a(w);
    for (int i = 0; i < w; ++i)
    {
        cin >> a[i].x;
        a[i].y = i + 1;
    }
    sort(a.begin(), a.end());
    for (int i = 1; i <= n; ++i)
    {
        int num;
        string pre;
        cin >> num >> pre;
        
        int l = 0, r = w - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(a[mid].x >= pre) r = mid;
            else l = mid + 1;
        }
        
        int idx = l + num - 1;
        if(idx >= w || a[idx].x.substr(0, SZ(pre)) != pre){
            cout << "-1\n";
        }
        else cout << a[idx].y << '\n';
    }
    return 0;
}

1927. 自动补全

题意

思路

代码