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

不爱听课的同学

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

自己的超时代码

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. inline void scan_d(int* num)   //快速输入函数代码
   
5. {
   
6.     char in;
   
7.     in = getchar();
   
8.     if (in == EOF) return;
   
9.     while (in != '-' && (in < '0' || in>'9')) in = getchar();
   
10.     if (in == '-') { *num = 0; }
    
11.     else *num = in - '0';
    
12.     while (in = getchar(), in >= '0' && in <= '9') {
    
13.         *num *= 10, * num += in - '0';
    
14.     }
    
15.     return;
    
16. }
    
17. 
    
18. int main()
    
19. {
    
20.     int N, score, A=0,B=0,C=0,D=0,E=0;
    
21.     scan_d(&N);
    
22.     for (int i = 1;i <= N;i++) {        //成绩处理部分
    
23.         scan_d(&score);
    
24.         if (score >= 90) A++;
    
25.         else if (score >= 80) B++;
    
26.         else if (score >= 70) C++;
    
27.         else if (score >= 60) D++;
    
28.         else E++;
    
29.     }
    
30.     printf("%d %d %d %d %d", A, B, C, D, E);
    
31.     return 0;
    
32. }
    

复制代码

答案代码

1. int a[120];    //创建包含每个成绩的数组
   
2. int main()
   
3. {
   
4.     int A = 0, B = 0, C = 0, D = 0, E = 0;
   
5.     int N = 0, score, i = 0;
   
6.     scan_d(&N);
   
7.     for (i = 1; i <= N; i++)
   
8.     {
   
9.         scan_d(&score);
   
10.         a[score]++;
    
11.     }
    
12.     i = 0;                   //成绩录入
    
13.     for (; i < 60; i++)
    
14.         E += a[i];
    
15.     for (; i < 70; i++)
    
16.         D += a[i];
    
17.     for (; i < 80; i++)
    
18.         C += a[i];
    
19.     for (; i < 90; i++)
    
20.         B += a[i];
    
21.     for (; i <= 100; i++)
    
22.         A += a[i];
    
23. 
    
24.     printf("%d %d %d %d %d", A, B, C, D, E);
    
25.     return 0;
    
26. }

复制代码

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

最佳答案

月排行榜 / 总排行榜

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 这样的语法。
这个代码里最耗执行时间的是循环    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]++;

1. int a[120];    //创建包含每个成绩的数组
   
2. int main()
   
3. {
   
4.     int A = 0, B = 0, C = 0, D = 0, E = 0;
   
5.     int N = 0, score, i = 0;
   
6.     scan_d(&N);
   
7.     for (i = 1; i <= N; i++)
   
8.     {
   
9.         scan_d(&score);
   
10.         a[score]++;
    
11.     }
    
12. 
    
13.     i = 0;                   //成绩录入
    
14.     for (; i < 60; i++)
    
15.         E += a[i];
    
16.     for (; i < 70; i++)
    
17.         D += a[i];
    
18.     for (; i < 80; i++)
    
19.         C += a[i];
    
20.     for (; i < 90; i++)
    
21.         B += a[i];
    
22.     for (; i <= 100; i++)
    
23.         A += a[i];
    
24.        
    
25.     printf("%d %d %d %d %d", A, B, C, D, E);
    
26.     return 0;
    
27. }

复制代码

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 这样的语法。
这个代 ...

谢谢大佬回答，我搞懂啦