PAT (Basic Level) Practice 1038 统计同成绩学生

题目链接

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

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

3 2 0

个人总结：

第一次提交测试点4运行超时。数组遍历多，时间复杂度过高。

第一次代码

#include<iostream>
using namespace std;
int main()
{
    int n,i,j,m,s,k=0;
    cin>>n;
    int* a=new int[n];
    for(i=0;i<n;i++)
        cin>>a[i];
    cin>>m;
    int* b=new int[m];
    for(i=0;i<m;i++,k++)
    {
        cin>>s;
        for(j=0;j<n;j++)
        {
            if(s==a[j])b[k]++;
        }
    }
    cout<<b[0];
    for(i=1;i<m;i++)
        cout<<" "<<b[i];
    delete[] a;
    delete[] b;
    return 0;
}

反思后，用101个整数型元素的数组装分数个数

改进代码

#include<iostream>
using namespace std;
int main()
{
    int a[101]={0},i,n,s,m,j;
    cin>>n;//分数个数
    for(i=0;i<n;i++)
    {
        cin>>s;//学生分数
        a[s]++;
    }
    cin>>m;
    for(i=0;i<m;i++)
    {
        cin>>j;//查询分数
        if(i)cout<<" ";
        cout<<a[j];
    }
}