NOIP小学堂(四)| 图书管理员

网友投稿 2019-04-14 12:30

https://cdn.china-scratch.com/timg/190416/12305R3I-0.jpg

本期小编带来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,下图展示了枚举的思想。

https://cdn.china-scratch.com/timg/190416/12305W116-1.jpg

(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