读完题目第一想法是trie树
,不过好像没怎么做过trie树的题,看y总给的知识点是二分排序,所以就有了如下思路;
但是但是,看完其他题解之后才坚定了我的想法,原来真的是这样排序,暴力啊!
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int w,n;
unordered_map<string,int>mp;
string str[30010];
int main(){
cin>>w>>n;
for(int i=1;i<=w;i++)
{
string s="";
cin>>s;
mp[s]=i;
str[i]=s;
}
sort(str+1,str+1+w);
for(int i=1;i<=w;i++)
cout<<str[i]<<" ";
puts("");
while(n--){
int a;
string pre;
cin>>a>>pre;
int p = lower_bound(str+1,str+1+w,pre)-str;
//cout<<p<<" 最左边"<<endl;
p = p + a -1;
//cout<<p<<" 最后一个"<<endl;
if(p < w && str[p].substr(0,pre.size()) == pre)
cout<<mp[str[p]]<<endl;
else
cout<<"-1"<<endl;
}
return 0;
}