洛谷P2412 查单词

传送门

题目背景

滚粗了的HansBug在收拾旧英语书，然而他发现了什么奇妙的东西。

题目描述

#udp2.T3如果遇到相同的字符串，输出后面的

蒟蒻HansBug在一本英语书里面找到了一个单词表，包含N个单词（每个单词内包含大小写字母）。现在他想要找出某一段连续的单词内字典序最大的单词。

输入格式

第一行包含两个正整数N、M，分别表示单词个数和询问个数。

接下来N行每行包含一个字符串，仅包含大小写字母，长度不超过15，表示一个单词。

再接下来M行每行包含两个整数x、y，表示求从第x到第y个单词中字典序最大的单词。

输出格式

输出包含M行，每行为一个字符串，分别依次对应前面M个询问的结果。

输入输出样例
输入 #1复制
5 5
absi
hansbug
lzn
kkk
yyy
1 5
1 1
1 2
2 3
4 4
输出 #1复制
yyy
absi
hansbug
lzn
kkk
说明/提示
样例说明：

第一次操作：在{absi,hansbug,lzn,kkk,yyy}中找出字典序最大的，故为yyy

第二次操作：在{absi}中找出字典序最大的，故为absi

第三次操作：在{absi,hansbug}中找出字典序最大的，故为hansbug

第四次操作：在{hansbug,lzn}中找出字典序最大的，故为lzn

第五次操作：在{kkk}中找出字典序最大的，故为kkk

数据规模：

注意事项：1.该题目单词字典序比对过程中大小写不敏感，但是输出必须输出原单词

2.该题目时间限制为0.2s

上代码：

#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct what{
	char a[16];//原本的字串
	int num;
	char b[16];//全变成小写的字串
}ha[50001];
bool cs(what x,what y){//排序
	for(int i=0;i<16;i++){
		if(x.b[i]>y.b[i]){
			return true;
		}else if(x.b[i]<y.b[i]){
			return false;
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>ha[i].a;
    	ha[i].num=i;
    	for(int j=0;j<15;j++){//把大写字母变成小写
    		if(ha[i].a[j]>='A'&&ha[i].a[j]<='Z'){
    			ha[i].b[j]=ha[i].a[j]+32;
			}else{
				ha[i].b[j]=ha[i].a[j];
			}
		}
	}
	sort(ha+1,ha+1+n,cs);
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		for(int i=1;i<=n;i++){
			if(ha[i].num>=x&&ha[i].num<=y){//从最大开始，第一个在范围内的ok
				cout<<ha[i].a<<endl;
				break;
			}
		}
	}
	return 0;
}
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