PAT乙级1038 || 统计同成绩学生（详解，C/C++示例，测试点分析）

Posted on In

统计同成绩学生

题目描述

本题要求读入 N 名学生的成绩，将获得某一给定分数的学生人数输出。

输入格式

输入在第 1 行给出不超过 $10^5$ 的正整数 N，即学生总人数。随后一行给出 N 名学生的百分制整数成绩，中间以空格分隔。最后一行给出要查询的分数个数 K（不超过 N 的正整数），随后是 K 个分数，中间以空格分隔。

输出格式

在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。

输入样例

1
2
3
10
60 75 90 55 75 99 82 90 75 50
3 75 90 88

输出样例

1
3 2 0

问题解决

解题思想

本题思路并不复杂，但是如果采用常规解法会很容易造成超时，而且费时费空间。我在刚开始遇到这个问题时虽然输出想到了用数组下标当作成绩，但是由于对输入的处理很一般，这导致后面的过程很复杂，最后还有一个测试点（测试点3）出现错误，错误的原因也很容易发现，这也可能是大家容易忽略的一个地方——k的范围，题目明确说明了k的范围不超过N，这也就隐含着k是可以超过101的，从而指定需要查询学生人数的分数可能会有重复，下面的代码1因没有处理这种情况从而导致最后一个测试点错误。

代码2充分考虑了用散列。因而分数都是百分制的，分数的范围时很小的，可以在输入的同时统计各分数的个数，当需要从指定分数查询学生人数时就可以直接输出。既节约了空间又节约了时间。

坑点提醒

最后一个测试点的k要大于101，会有重复需要查询的分数出现，这就要求输出的时候也要按顺序重复输出学生人数。下面的代码1没有考虑k大于101的情况，代码2考虑了。

代码示例（C/C++）

代码1

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//方法1，
#include <cstdio>
#include <algorithm>
#define MAXN 100001
using namespace std;
//统计得分等于指定分数的学生人数的结构体类型
struct count_score
{
    int a = 0;  //得分等于指定分数的学生人数
    int b = 0;  //输入分数的顺序
}score[101];    //下标为分数
bool cmp(count_score x,count_score y)
{
    return x.b < y.b;
}
int main()
{
    int n;  //学生总人数
    scanf("%d",&n);
    int grade[MAXN];    //成绩
    for(int i = 0; i < n; i++){
        scanf("%d",&grade[i]);
    }
    int k;  //要查询的分数的个数
    scanf("%d",&k);
    int j = 1;  //标记输入分数的顺序
    for(int i = 0; i < k; i++){
        int temp;   //temp接收输入分数
        scanf("%d",&temp);
        score[temp].b = j++;
    }
    for(int i = 0; i < n; i++){
        if(score[grade[i]].b){
            score[grade[i]].a++;
        }
    }
    sort(score,score + 101,cmp);
    for(int i = 101 - k; i < 101; i++){
        printf("%d",score[i].a);
        if(i != 100){
            printf(" ");
        }
    }
    return 0;
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
using namespace std;
int main()
{
    int n,grade[101] = {0}; //grade[]下标为分数，内容为该分数的个数
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        int temp;   //临时接收输入的分数
        scanf("%d",&temp);
        grade[temp]++;  //统计该分数的个数
    }
    int k;
    scanf("%d",&k);
    for(int i = 0; i < k; i++){
        int temp;   //临时接收输入的分数
        scanf("%d",&temp);
        printf("%d",grade[temp]);   //输出该分数的个数
        if(i != k - 1){
            printf(" ");
        }
    }
    return 0;
}

题目来源：PAT乙级1038
作者：CHEN, Yue
单位：浙江大学

稀罕作者