[已解决]时间超时

巴巴鲁

蓝桥杯上的一道题，总是说时间超时，难道还有更简单的写法？！
提示：时间超限：运行超出时间限制，请检查是否有死循环或程序算法效率低。
[code]#include <stdio.h>

int main(void)
{
       
        int n, k, T, i = 1, j;
        int sum = 1, count = 1, num = 1;
        scanf("%d %d %d", &n, &k, &T);
       
        for(j = 1; j <= n; ++j)
        {
                if(i == T)
                {
                        break;
                }
               
                num += count;
                count++;
                if(num > k)
                {
                        num = num + count - k;
                }
               
               
                if(j == n)
                {
                        sum += num;
                        i++;
                        j = 1;
                }
        }
       
        printf("%d", sum);
        return 0;
} [\code]

最佳答案

月排行榜 / 总排行榜

baige

2021-3-19 20:50:21

这一种比上一种简单，溢出处理也比较容易，也是等差数列求和

1. #include <stdio.h>
   
2. #define LL long long int
   
3. 
   
4. int main(void) {
   
5.         int i = 1;
   
6.         LL sum = 1, x, add = 1, n, k, t;
   
7.         scanf("%lld%lld%lld",&n,&k,&t);
   
8.         while (i < t) {
   
9.                 x = add + ((i-1)*n + 1 + i*n)*n/2; // 得到这次这个人所报的数字
   
10. 
    
11.                 i++;  // 过这个人的次数加1
    
12.                 x = x % k; //当大于k的部分需要返回
    
13.                 sum += x; //数字和
    
14.                 add = x; // 返回
    
15.         }
    
16.         printf("%lld",sum);
    
17.         return 0;
    
18. }
    

复制代码

跳转到最佳答案楼层

zip...

太难了，头发又掉了两根。

baige

C++不想写了溢出
思路：https://wenda.so.com/q/1383384369068994

1. n, k, t = input().split()
   
2. n, k, t = int(n), int(k), int(t);
   
3. ans = 1
   
4. for i in range(1, t):
   
5.     ans += ((i*n+1)*(i*n)//2+1)%k
   
6. print(ans)
   

复制代码

巴巴鲁

baige 发表于 2021-3-19 19:42
C++不想写了溢出
思路：https://wenda.so.com/q/1383384369068994

这是考的数学还是编程啊

baige

别的比赛数学更难

baige

这一种比上一种简单，溢出处理也比较容易，也是等差数列求和

1. #include <stdio.h>
   
2. #define LL long long int
   
3. 
   
4. int main(void) {
   
5.         int i = 1;
   
6.         LL sum = 1, x, add = 1, n, k, t;
   
7.         scanf("%lld%lld%lld",&n,&k,&t);
   
8.         while (i < t) {
   
9.                 x = add + ((i-1)*n + 1 + i*n)*n/2; // 得到这次这个人所报的数字
   
10. 
    
11.                 i++;  // 过这个人的次数加1
    
12.                 x = x % k; //当大于k的部分需要返回
    
13.                 sum += x; //数字和
    
14.                 add = x; // 返回
    
15.         }
    
16.         printf("%lld",sum);
    
17.         return 0;
    
18. }
    

复制代码

人造人

错误太多，边界，步距，循环次数，大部分都错了

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.     //int n, k, T, i = 1, j;
   
6.     int n, k, T, i = 0, j;
   
7.     //int sum = 1, count = 1, num = 1;
   
8.     int sum = 0, count = 1, num = 1;
   
9.     scanf("%d %d %d", &n, &k, &T);
   
10. 
    
11.     //for(j = 1; j <= n; ++j)
    
12.     for(j = 0; j <= n; ++j)
    
13.     {
    
14.         if(i == T)
    
15.         {
    
16.             break;
    
17.         }
    
18. 
    
19.         //num += count;
    
20.         //count++;
    
21.         if(num > k)
    
22.         {
    
23.             //num = num + count - k;
    
24.             num = num - k;
    
25.         }
    
26. 
    
27. 
    
28.         //if(j == n)
    
29.         if(j == 0 || j == n)
    
30.         {
    
31.             sum += num;
    
32.             i++;
    
33.             //j = 1;
    
34.             j = 0;
    
35.         }
    
36. 
    
37.         num += count;
    
38.         count++;
    
39.     }
    
40. 
    
41.     printf("%d", sum);
    
42.     return 0;
    
43. }
    

复制代码

愷龍

1. #include <stdio.h>
   
2. int main()
   
3. {
   
4.     int n, k, T;
   
5.     long long sum = 1, t=1, a=1;
   
6.     scanf("%d%d%d", &n, &k, &T);
   
7.     int i;
   
8.     for(i = 1; i < T; ++i)
   
9.     {
   
10.         t = (((a+a+n-1)*n/2)+t)%k;
    
11.         sum += t;
    
12.         a += n;
    
13.     }
    
14.     printf("%lld\n", sum);
    
15.     return 0;
    
16. }

复制代码

人造人

1. #include <stdio.h>
   
2. 
   
3. int main(void) {
   
4.     size_t n, k, T;
   
5.     size_t sum = 0, num = 1, count = 1;
   
6.     scanf("%lu%lu%lu", &n, &k, &T);
   
7.     for(size_t i = 0; i < T; ++i) {
   
8.         sum += num;
   
9.         for(size_t j = 0; j < n; ++j) {
   
10.             num += count++;
    
11.             if(num >= k) num = num - k;
    
12.         }
    
13.     }
    
14.     printf("%lu\n", sum);
    
15.     return 0;
    
16. }
    

复制代码

巴巴鲁

zip... 发表于 2021-3-19 19:30
太难了，头发又掉了两根。

这个不难，难就难在使代码最高效

巴巴鲁

人造人 发表于 2021-3-19 20:52
错误太多，边界，步距，循环次数，大部分都错了

没有吧，我初始条件就赋值1，j开始少循环一次，

巴巴鲁

人造人 发表于 2021-3-19 20:52
错误太多，边界，步距，循环次数，大部分都错了

关键是超时，好像要是最高效的

巴巴鲁

愷龍 发表于 2021-3-19 20:53

楼上先发的，就把最佳给他了

人造人

巴巴鲁 发表于 2021-3-19 22:24
关键是超时，好像要是最高效的

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5. 
   
6.     int n, k, T, i = 1, j;
   
7.     int sum = 1, count = 1, num = 1;
   
8.     scanf("%d %d %d", &n, &k, &T);
   
9. 
   
10.     for(j = 1; j <= n; ++j)
    
11.     {
    
12.         if(i == T)
    
13.         {
    
14.             break;
    
15.         }
    
16. 
    
17.         num += count;
    
18.         count++;
    
19.         if(num > k)
    
20.         {
    
21.             num = num + count - k;
    
22.         }
    
23. 
    
24. 
    
25.         printf("%d\n", num);
    
26.         if(j == n)
    
27.         {
    
28.             printf("    %d\n", num);
    
29.             sum += num;
    
30.             i++;
    
31.             j = 1;
    
32.         }
    
33.     }
    
34. 
    
35.     printf("%d", sum);
    
36.     return 0;
    
37. }
    

复制代码

1. 3 13 3
   
2. 2
   
3. 4
   
4. 7
   
5.     7
   
6. 11
   
7. 9
   
8.     9
   

复制代码

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.     //int n, k, T, i = 1, j;
   
6.     int n, k, T, i = 0, j;
   
7.     //int sum = 1, count = 1, num = 1;
   
8.     int sum = 0, count = 1, num = 1;
   
9.     scanf("%d %d %d", &n, &k, &T);
   
10. 
    
11.     //for(j = 1; j <= n; ++j)
    
12.     for(j = 0; j <= n; ++j)
    
13.     {
    
14.         if(i == T)
    
15.         {
    
16.             break;
    
17.         }
    
18. 
    
19.         //num += count;
    
20.         //count++;
    
21.         if(num > k)
    
22.         {
    
23.             //num = num + count - k;
    
24.             num = num - k;
    
25.         }
    
26. 
    
27. 
    
28.         printf("%d\n", num);
    
29.         //if(j == n)
    
30.         if(j == 0 || j == n)
    
31.         {
    
32.             printf("    %d\n", num);
    
33.             sum += num;
    
34.             i++;
    
35.             //j = 1;
    
36.             j = 0;
    
37.         }
    
38. 
    
39.         num += count;
    
40.         count++;
    
41.     }
    
42. 
    
43.     printf("%d", sum);
    
44.     return 0;
    
45. }
    

复制代码

1. 3 13 3
   
2. 1
   
3.     1
   
4. 2
   
5. 4
   
6. 7
   
7.     7
   
8. 11
   
9. 3
   
10. 9
    
11.     9
    

复制代码

人造人

提问，为什么这3个程序的输出不一样？

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.       
   
6.         int n, k, T, i = 1, j;
   
7.         int sum = 1, count = 1, num = 1;
   
8.         scanf("%d %d %d", &n, &k, &T);
   
9.       
   
10.         for(j = 1; j <= n; ++j)
    
11.         {
    
12.                 if(i == T)
    
13.                 {
    
14.                         break;
    
15.                 }
    
16.                
    
17.                 num += count;
    
18.                 count++;
    
19.                 if(num > k)
    
20.                 {
    
21.                         num = num + count - k;
    
22.                 }
    
23.                
    
24.                
    
25.                 if(j == n)
    
26.                 {
    
27.                         sum += num;
    
28.                         i++;
    
29.                         j = 1;
    
30.                 }
    
31.         }
    
32.       
    
33.         printf("%d", sum);
    
34.         return 0;
    
35. }
    

复制代码

1. 4 14 4
   
2. 57

复制代码

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.     //int n, k, T, i = 1, j;
   
6.     int n, k, T, i = 0, j;
   
7.     //int sum = 1, count = 1, num = 1;
   
8.     int sum = 0, count = 1, num = 1;
   
9.     scanf("%d %d %d", &n, &k, &T);
   
10. 
    
11.     //for(j = 1; j <= n; ++j)
    
12.     for(j = 0; j <= n; ++j)
    
13.     {
    
14.         if(i == T)
    
15.         {
    
16.             break;
    
17.         }
    
18. 
    
19.         //num += count;
    
20.         //count++;
    
21.         if(num > k)
    
22.         {
    
23.             //num = num + count - k;
    
24.             num = num - k;
    
25.         }
    
26. 
    
27. 
    
28.         //if(j == n)
    
29.         if(j == 0 || j == n)
    
30.         {
    
31.             sum += num;
    
32.             i++;
    
33.             //j = 1;
    
34.             j = 0;
    
35.         }
    
36. 
    
37.         num += count;
    
38.         count++;
    
39.     }
    
40. 
    
41.     printf("%d", sum);
    
42.     return 0;
    
43. }
    

复制代码

1. 4 14 4
   
2. 30

复制代码

1. #include <stdio.h>
   
2. #define LL long long int
   
3. 
   
4. int main(void) {
   
5.         int i = 1;
   
6.         LL sum = 1, x, add = 1, n, k, t;
   
7.         scanf("%lld%lld%lld",&n,&k,&t);
   
8.         while (i < t) {
   
9.                 x = add + ((i-1)*n + 1 + i*n)*n/2; // 得到这次这个人所报的数字
   
10. 
    
11.                 i++;  // 过这个人的次数加1
    
12.                 x = x % k; //当大于k的部分需要返回
    
13.                 sum += x; //数字和
    
14.                 add = x; // 返回
    
15.         }
    
16.         printf("%lld",sum);
    
17.         return 0;
    
18. }
    

复制代码

1. 4 14 4
   
2. 30

复制代码

巴巴鲁

人造人 发表于 2021-3-20 00:05
提问，为什么这3个程序的输出不一样？

啊，抱歉，我思路有问题

yayc_zcyd

哈哈，你也要考蓝桥杯啊

han125416866

巴巴鲁

yayc_zcyd 发表于 2021-3-21 21:45
哈哈，你也要考蓝桥杯啊

哈哈，是的，同道中人吗？

yayc_zcyd

巴巴鲁 发表于 2021-3-23 12:28
哈哈，是的，同道中人吗？

必须的，但是我发现蓝桥杯考的几乎全是算法