空间换时间的思想

题目描述

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

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

3 2 0

开始解题

这题最容易想到的就是判断那k个分数是否存在于(in)前面的N个分数列表中，代码如下，但是最后一个测试点运行超时，原来题目限时250ms。

#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;++i)
        scanf("%d",&a[i]);

    int k;
    scanf("%d",&k);
    int b[k];
    int count[k]={0};
    for(int i=0;i<k;++i)
    {
        scanf("%d",&b[i]);
        for(int m=0;m<n;++m)
        {
            if(b[i]==a[m])
            {
                count[i]++;
            }
        }
    }
    for(int i=0;i<k;++i)
    {
        printf("%d",count[i]);
        if(i<k-1)
            printf(" ");
    }


}

和前面的那题【挖掘机技术哪家强】一样，这里也可以采用空间换时间的思想，代码如下

#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    //开个大数组
    int s[100001];
    for(int i=0;i<n;++i)
    {
        scanf("%d",&a[i]);
        s[a[i]]++;
    }

    int k;
    scanf("%d",&k);
    int b[k];
    for(int i=0;i<k;++i)
    {
        scanf("%d",&b[i]);
        printf("%d",s[b[i]]);
        if(i<k-1)
            printf(" ");

    }
}

AC!