为什么发这道题呢,因为这道题官方标签是字符串和排序,实际上可以不用,反而更简单
先看下题

[NOIP2017 普及组] 图书管理员

题目背景

NOIP2017 普及组 T2

题目描述

图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个正整数。 每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。 小 D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他需要的书,请输出 -1

输入格式

第一行,包含两个正整数 n,qn , q,以一个空格分开,分别代表图书馆里 书的数量和读者的数量。

接下来的 nn 行,每行包含一个正整数,代表图书馆里某本书的图书编码。

接下来的 qq 行,每行包含两个正整数,以一个空格分开,第一个正整数代表图书馆 里读者的需求码的长度,第二个正整数代表读者的需求码。

输出格式

$ q$ 行,每行包含一个整数,如果存在第 ii 个读者所需要的书,则在第 ii 行输出第 ii 个读者所需要的书中图书编码最小的那本书的图书编码,否则输出1-1

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
5 5 
2123
1123
23
24
24
2 23
3 123
3 124
2 12
2 12

样例输出 #1

1
2
3
4
5
23 
1123
-1
-1
-1

提示

数据规模与约定

对于 20%20\% 的数据,1n21 ≤ n ≤ 2

另有 20%20\% 的数据,q=1q = 1

另有 20%20\% 的数据,所有读者的需求码的长度均为 11

另有 20%20\% 的数据,所有的图书编码按从小到大的顺序给出。

对于 100%100\% 的数据,1n1000,1q10001 ≤ n ≤ 1000,1 ≤ q ≤ 1000,所有的图书编码和需求码均不超过 10710^7

思考

NOIP 2017普及组 第2题。
主要就是比较一个数后几位长度是否与给定值相等,那么很容易想到的是字符串,比较后面几位,写起来费事一点
我翻遍了洛谷题解区,清一色的字符串+STL里的快排,其实不需要,我们先理解一个性质
1234 这个数,如何取后面2位,也就是34?通过数学里的方法,我们只需要对1234 mod 100就能求到是34。同样如果对1234取后面3位的234,只需要 mod1000即可。1000是10的3次方,我们也正好要后面3位数。
所以:一个数需要取末尾n位数,就可以用这个数mod(10^n)
明白这个后,那就很简单了,设某个读者需要的书末尾长度是len,那么pow(10,len)就是这个mod数,也就是用书籍号码去mod它。
对于排序,也不需要那么复杂,因为我们只需要最小的,所以一开始int一个非常大的数,然后只要发现符合规则的数且小于这个初始值的,赋值给它就可以。

代码

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
#include "bits/stdc++.h"
using namespace std;
const int maxn = 1e3+5;
int n,q; //n:书的数量 q:读者数量
int book[maxn]; //存书的编号
int main () {
cin>>n>>q;
for (int i=1;i<=n;i++) {
cin>>book[i]; //读取书的编号
}
for (int i=1;i<=q;i++) {
int len,num; //长度,末尾数字
cin>>len>>num;
int get_num = 99999999; //初始值开大点
for (int j=1;j<=n;j++) {
int mod = pow(10,len); //明白一个性质,如一个数需要取末尾n位数,就可以用这个数mod(10^n)
int end = book[j]%mod; //book[j]的最后len位数
if (end==num && book[j]<get_num) { //我们要选最小的
get_num = book[j];
}
}
if (get_num==99999999) cout<<-1<<endl; //无结果
else {
cout<<get_num<<endl; //输出
}
}
return 0;
}

理解了思考那一段之后,我想这个代码就很容易看懂了。