第一题 [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 ;
}

结果：