第一题 [NOIP2017]图书管理员
题目
题目描述
图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个正整数。
每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。
小 D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他需要的书,请输出-1。
输入描述:
输入的第一行,包含两个正整数 n 和 q,以一个空格分开,分别代表图书馆里书的数量和读者的数量。
接下来的 n 行,每行包含一个正整数,代表图书馆里某本书的图书编码。
接下来的 q 行,每行包含两个正整数,以一个空格分开,第一个正整数代表图书馆里读者的需求码的长度,第二个正整数代表读者的需求码。
输出描述:
输出有 q 行,每行包含一个整数,如果存在第 i 个读者所需要的书,则在第 i 行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码,否则输出-1。
示例1
输入
5 5 2123 1123 23 24 24 2 23 3 123 3 124 2 12 2 12
输出
23 1123 -1 -1 -1
说明
第一位读者需要的书有 2123、1123、23,其中 23 是最小的图书编码。
第二位读者需要的书有 2123、1123,其中 1123 是最小的图书编码。
对于第三位,第四位和第五位读者,没有书的图书编码以他们的需求码结尾,即没有他们需要的书,输出-1。
备注:
对于 20%的数据,1 ≤ n ≤ 2。 另有 20%的数据,q= 1。
另有 20%的数据,所有读者的需求码的长度均为1。
另有 20%的数据,所有的图书编码按从小到大的顺序给出。
对于 100%的数据,1≤n ≤1,000,1 ≤ q ≤ 1,000,所有的图书编码和需求码均不超过 10,000,000。
思路
首先我们看到的是:这是一个字符串匹配的题目。但是由于字符串都比较小,最多才4位,完全可以跑O(n),由于是子串匹配,为了逐位比较方便,可以存string或者char,但是又因位需要输出最小的,那就应该首选string了。那如果string不会用怎么办?我给大家带来一个用int存的解法。因为在题目种已经给出我们查询的末尾位数了,所以我们在用int定义所有编号后,对其编号进行10的位数次方取模,这样的结果就是我们的末尾数了,末尾数可以求出来,那么这道题就迎刃而解了。
需要注意的是,我们可以先使用一个sort函数对编号进行整体的排序,这样就可以保证从前往后输出时先输出的是较小的编号了。
AC
#include<iostream> #include<algorithm> using namespace std ; int a[1010] ; int main() { int n, q ; cin >> n >> q ; for(int i=0; i<n; i++) { cin >> a[i] ; } sort(a,a+n) ; //排序 while(q--) //q行 { int num, sum , s=1 ; cin >> num >> sum ; while(num--) //计算10的位数次方 s=s*10 ; int k = 0 ; for(int j=0; j<n; j++) { if(a[j]%s == sum) //进行取模比较 { cout << a[j] << endl ; break; } else { k++ ; } } if(k == n) cout << "-1" << endl ; //判断是否有匹配的图书 } return 0 ; }
运行结果:
第二题 [NOIP2009]分数线划定
题目
题目描述:
世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才,A 市对所有报名的选手进行了笔试。
笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定。
即如果计划录取m名志愿者,则面试分数线为排名第m*150%(向下取整)名的选手的分数。
而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。
现在就请你编写程序划定面试分数线,并输出所有进入面试的选手的报名号和笔试成绩。
输入描述:
第一行,两个整数n,m(5≤n≤5000,3≤m≤n),中间用一个空格隔开,其中n 表示报名参加笔试的选手总数,m表示计划录取的志愿者人数。
输入数据保证m*150%向下取整后小于等于n。
第二行到第n+1行,每行包括两个整数,中间用一个空格隔开,分别是选手的报名号k(1000≤k≤9999)和该选手的笔试成绩s(1≤s≤100)。
数据保证选手的报名号各不相同。
输出描述:
第一行,有两个整数,用一个空格隔开,第一个整数表示面试分数线;第二个整数为进入面试的选手的实际人数。
从第二行开始,每行包含两个整数,中间用一个空格隔开,分别表示进入面试的选手的报名号和笔试成绩。
按照笔试成绩从高到低输出,如果成绩相同,则按报名号由小到大的顺序输出。
思路
通过读题判断这道题就是一道简单数学题+结构体排序。这时我们要注意的是题目就是预定录取人数就是m * 1.5,然后压线同分的人全要。
那么这里我们使用数组或者结构体都是可以做的,首先我们创建出一个结构体,在里面设置两个变量用来表示编号和成绩,之后我们创建出一个结构体数组用来存放所有数据,注意的是在存入数据时,我们可以从0开水存入,也可以从1,这两种方法都是可以的,不过到后面会有个加1减1的问题。之后我们对调用sort对结构体进行排序,先按成绩从大到小排,当成绩相同的时候,我们再按编号从小到大去排序。
题目要求同分数的人全部录取,所以我们在计算完录取人数时,应去判断下方是否有与其同分的分员,之后在调整录取人数即可。
AC
#include<iostream> #include<algorithm> using namespace std ; struct Node{ //创建结构体 int s ; int num ; }; bool cmp(Node &u, Node &v) { if (u.num == v.num) return u.s < u.s ; return u.num > v.num ; } Node a[5010] ; int main() { int n, m ; cin >> n >> m ; for(int i=0; i<n; i++) { cin >> a[i].s >> a[i].num ; } sort(a, a+n, cmp) ; //排序 int rank = m * 1.5 ; //计算录取人数 int score = a[rank].num ; while (score == a[rank].num) rank++; //判断是否有同分人员 cout << score << " " << rank - 1 << endl; for (int i = 1; i < rank; i++) cout << a[i].s << " " << a[i].num << endl; return 0 ; }
运行结果
第三题 [NOIP2007]奖学金
题目
题目描述
某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学 排在前面,这样,每个学生的排序是唯一确定的。
任务:先根据输入的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前五名名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分) 是:
7 279
5 279
这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ,但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279
7 279
则按输出错误处理,不能得分。
输入描述:
第1行为一个正整数n,表示该校参加评选的学生人数。
第2到n+1行,每行有3个用空格隔开的数字,每个数字都在O到100之间z第1行的3个数 字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为l~n (恰好是输入数据的行号减1)。
所给的数据都是正确的,不必检验。
输出描述:
共有5行,每行是两个用空格隔开的正整数,依次表示前5名学生的学号和总分。
示例1
输入
6 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98
输出:
6 265 4 264 3 258 2 244 1 237
示例2
输入
8 80 89 89 88 98 78 90 67 80 87 66 91 78 89 91 88 99 77 67 89 64 78 89 98
输出
8 265 2 264 6 264 1 258 5 258
备注:
50%的数据满足: 各学生的总成绩各不相同
100%的数据满足: 6<=n<=300
思路
这道题目我们首先先创建一个结构体,在里面设置出id和语数英成绩以及总成绩,然后在照例创建一个结构体数组,去存放这些成绩,利用sort函数对其进行一个排序,最后排序完成后按照题目的要求输出即可。
AC
#include<iostream> #include<algorithm> using namespace std ; struct Node{ //创建结构体 int id ;//学号 int chinese ;//语文成绩 int math ;//数学成绩 int english ;//英语成绩 int sum ;//总成绩 }; //声明结构体排序函数 bool cmp(Node &u, Node &v) { u.sum = u.chinese + u.math + u.english ; v.sum = v.chinese + v.math + v.english ; if(u.sum == v.sum)//总分相同时 { if(u.chinese == v.chinese)//语文成绩相同时,按学号从小到大排 { return u.id < v.id ; } else return u.chinese > v.chinese ;//语文成绩不同时,按语文成绩从大到小排 } else return u.sum > v.sum ;//总分不同时,按总分从大到小排 } Node a[310] ; int main() { int n ;//学生人数 cin >> n ; for(int i=0; i<n; i++) { cin >> a[i].chinese >> a[i].math >> a[i].english ; a[i].id = i+1 ; } sort(a, a+n, cmp) ; for(int i=0; i<5; i++) { cout << a[i].id << " " << a[i].sum << endl ; } return 0 ; }
结果: