[已解决]高效输入和高效算法

不爱听课的同学

自己找了快速输入的代码，但算法过程太慢超时了，看了一下答案不懂为什么答案比较快

自己的超时代码

#include <iostream>
using namespace std;

inline void scan_d(int* num)   //快速输入函数代码
{
    char in;
    in = getchar();
    if (in == EOF) return;
    while (in != '-' && (in < '0' || in>'9')) in = getchar();
    if (in == '-') { *num = 0; }
    else *num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        *num *= 10, * num += in - '0';
    }
    return;
}

int main()
{
    int N, score, A=0,B=0,C=0,D=0,E=0;
    scan_d(&N);
    for (int i = 1;i <= N;i++) {        //成绩处理部分
        scan_d(&score);
        if (score >= 90) A++;
        else if (score >= 80) B++;
        else if (score >= 70) C++;
        else if (score >= 60) D++;
        else E++;
    }
    printf("%d %d %d %d %d", A, B, C, D, E);
    return 0;
}

答案代码

int a[120];    //创建包含每个成绩的数组
int main()
{
    int A = 0, B = 0, C = 0, D = 0, E = 0;
    int N = 0, score, i = 0;
    scan_d(&N);
    for (i = 1; i <= N; i++)
    {
        scan_d(&score);
        a[score]++;
    }
    i = 0;                   //成绩录入
    for (; i < 60; i++)
        E += a[i];
    for (; i < 70; i++)
        D += a[i];
    for (; i < 80; i++)
        C += a[i];
    for (; i < 90; i++)
        B += a[i];
    for (; i <= 100; i++)
        A += a[i];

    printf("%d %d %d %d %d", A, B, C, D, E);
    return 0;
}

为什么答案的方法更快，而我的方法超时了，答案是用了某种算法吗？还有没有其他解法？

最佳答案

月排行榜 / 总排行榜

sunrise085

2020-11-18 15:32:16

不知道你是否理解答案的执行过程，这是一分一档汇总人数，然后再按照划分层次再次汇总。
a[score]就是分数为score的人数，后面按照数组a的下标进行汇总即可。

你的写法在N特别大的时候就会显得很慢。
因为你的程序运算次数多，每输入一个分数，需要执行1~4次比较运算，然后再执行一次加法运算，总运算次数是2N~4N，此外，分支也会很消耗时间，是的程序更慢
答案，每输入一个分数执行一次加法，输入结束后，执行100加法进行人数汇总，总的计算次数是N+100

跳转到最佳答案楼层

xieglt

首先，答案代码的语法是错的，没有  E += a 这种语法，只有 E += *(a+i) 或者 E+= a[i] 这样的语法。
这个代码里最耗执行时间的是循环    for (i = 1; i <= N; i++)  ，
所以，这个循环里执行的语句越少，总的执行时间越快。

a[score]++;
这行代码的意思是统计不同成绩的数量，比如说输入的第一次输入成绩是61，那么 a[61] ++
表示 61 这个分数有了 1 人，再输入一个89，则 a[89]++，表示 89 这个分数有了 1 人。
输入循环结束后，再将数组 a 中每个分数段中的人数求和则可获得每个分数段的总人数了。

后面的5个循环 i 从 0 循环到 100，只执行了100次加法，如果 N > 10000，那么，这个100次循环几乎可以忽略。
scan_d(&score); 这行代码是一样的，不对执行时间产生影响。

而你的代码里的一堆 if 执行时间必然超过 a[score]++;

int a[120];    //创建包含每个成绩的数组
int main()
{
    int A = 0, B = 0, C = 0, D = 0, E = 0;
    int N = 0, score, i = 0;
    scan_d(&N);
    for (i = 1; i <= N; i++)
    {
        scan_d(&score);
        a[score]++;
    }

    i = 0;                   //成绩录入
    for (; i < 60; i++)
        E += a[i];
    for (; i < 70; i++)
        D += a[i];
    for (; i < 80; i++)
        C += a[i];
    for (; i < 90; i++)
        B += a[i];
    for (; i <= 100; i++)
        A += a[i];
        
    printf("%d %d %d %d %d", A, B, C, D, E);
    return 0;
}

sunrise085

不知道你是否理解答案的执行过程，这是一分一档汇总人数，然后再按照划分层次再次汇总。
a[score]就是分数为score的人数，后面按照数组a的下标进行汇总即可。

你的写法在N特别大的时候就会显得很慢。
因为你的程序运算次数多，每输入一个分数，需要执行1~4次比较运算，然后再执行一次加法运算，总运算次数是2N~4N，此外，分支也会很消耗时间，是的程序更慢
答案，每输入一个分数执行一次加法，输入结束后，执行100加法进行人数汇总，总的计算次数是N+100

不爱听课的同学

sunrise085 发表于 2020-11-18 15:32
不知道你是否理解答案的执行过程，这是一分一档汇总人数，然后再按照划分层次再次汇总。
a[score]就是分数 ...

我明白啦，多谢大佬解答

不爱听课的同学

xieglt 发表于 2020-11-18 15:31
首先，答案代码的语法是错的，没有  E += a 这种语法，只有 E += *(a+i) 或者 E+= a 这样的语法。
这个代 ...

谢谢大佬回答，我搞懂啦