本期小编带来2017年NOIP普及组T2难度题目图书管理员，本题目涉及C++数组基本数据结构和入门的枚举算法思想，难度适中。NOIP小学堂在每期的文章中都将挑选一到NOIP真题进行讲解，有易有难，同时剖析知识点和解题思路。当然啦，时不时也会科普一些C++知识要点，有兴趣的小伙伴可以持续关注本号哟~！

——

1

 题目 

——

图书管理员

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

输入格式:

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

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

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

输出格式:

输出文件有 q 行，每行包含一个整数，如果存在第 i 个读者所需要的书，则在第 i 行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码，否则输出-1。

样例输入:

5 5

2123

1123

23

24

24

2 23

3 123

3 124

2 12

2 12

样例输出:

23

1123

-1

-1

-1 

提示:

【数据规模与约定】

对于 20%的数据，1 ≤ n ≤ 2。

另有 20%的数据，q = 1。

另有 20%的数据，所有读者的需求码的长度均为 1。

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

对于 100%的数据，1 ≤ n ≤ 1,000，1 ≤ q ≤ 1,000，所有的图书编码和需求码均 不超过 10,000,000。

——

2

 剖析 

——

考察点： 输入输出，取余操作应用，数组，枚举遍历

思路：

（1）先观察题目的输入条件，我们首先需要存储的数据将会是图书馆里面各个图书的编码，图书编码是一串数字，且每个图书编码和需求码均不超过10000000。因此我们可以直接使用int来存储图书编码。图书馆里的图书编码将会形成一个int数组books_num，需求码也会形成一个int数组need_num。此外，输入中涉及图书编码的长度，因此对应于need_num数组将会有一个int数组need_len用于存储需求码长度。

（2）我们先来思考一个问题，对于一本需求的书，假设它的编码为a，我们怎么在一堆书中找到以a为结尾编码的图书呢？其实可以想一个日常的事情，我们现在有一筐苹果，想找找看里面有没有坏的，是不是最简单的就是把苹果都挨个看一遍呢。同理，其实对于在一堆书中找到以a为结尾编码的图书，我们也可以挨个找。根据输入的例子来看，我们再假设a为23，图书馆里有的书码为2123,1123,23,24，下图展示了枚举的思想。

（3）那么如何确定需求书码和图书编码匹配呢？以a为结尾编码，假设a的长度为2，对于图书馆里面的书编码b，b的编码大小肯定要大于等于a的编码大小吧？否则怎么样都无法匹配上对吧？毕竟b必须是以a结尾的数字！好了，假设满足了b的大小大于等于a，那么如何确定b是以a结尾的呢？神奇的取余操作可以帮助到我们，由于题目给出了a的长度s，那么同学们，思考下面的式子：

   b % (10^s)  （10^s意思为10的s次方）

假设a为23，b为2123，那么2123%（10^2）是不是等于23呐？！答案明显是的，因为取余操作可以帮我们提取出一个数字的后几位组成的数字，这是一个技巧，小本子拿出来记下吧 ^ ^。

——

3

 程序 

——

#include#includeusing namespace std;
int books_num[1005];int need_num[1005];int need_len[1005];
int main(){//处理数据输入和存储int n,q;cin>>n>>q;for(int i=0;i>books_num[i];}for(int i=0;i>need_len[i]>>need_num[i];}//对于每一个读者需求的图书，进行遍历枚举操作for(int i=0;i= need_num[i]){if( (books_num[j]%(int)(pow(10,need_len[i]))) == need_num[i] ){                    //起初result初始化为-1，需要做特殊判断if(result == -1){result = books_num[j];}else{if(result>books_num[j]){result = books_num[j];                        }}}}}//输出最佳匹配结果cout<<result<<endl;}return 0;}

4

总结

NOIP普及组题目分为四个难度等级，T1一般为水题，考验同学们对C++语言的基本了解和对题意的理解。T2相比T1来说会增加基础数据结构和算法以及现实问题建模考察（如果将题目问题转化为程序可表示的内容），T2也是在普及组中拿分的重点，因为T3和T4题目在算法难度和编程技巧要求上会开始变得高起来。

——

不积跬步
无以千里

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com