论坛 › C\C++交流 › 时间超时

巴巴鲁 发表于 2021-3-19 19:07:44

时间超时

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

zip... 发表于 2021-3-19 19:30:53

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

baige 发表于 2021-3-19 19:42:53

本帖最后由 baige 于 2021-3-19 20:08 编辑

C++不想写了溢出
思路：https://wenda.so.com/q/1383384369068994
n, k, t = input().split()
n, k, t = int(n), int(k), int(t);
ans = 1
for i in range(1, t):
    ans += ((i*n+1)*(i*n)//2+1)%k
print(ans)

巴巴鲁 发表于 2021-3-19 20:09:24

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

这是考的数学还是编程啊{:10_243:}

baige 发表于 2021-3-19 20:16:51

别的比赛数学更难

baige 发表于 2021-3-19 20:50:21

本帖最后由 baige 于 2021-3-19 20:51 编辑

这一种比上一种简单，溢出处理也比较容易，也是等差数列求和
#include <stdio.h>
#define LL long long int

int main(void) {
        int i = 1;
        LL sum = 1, x, add = 1, n, k, t;
        scanf("%lld%lld%lld",&n,&k,&t);
        while (i < t) {
                x = add + ((i-1)*n + 1 + i*n)*n/2; // 得到这次这个人所报的数字

                i++;// 过这个人的次数加1
                x = x % k; //当大于k的部分需要返回
                sum += x; //数字和
                add = x; // 返回
        }
        printf("%lld",sum);
        return 0;
}

人造人 发表于 2021-3-19 20:52:31

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

#include <stdio.h>

int main(void)
{
    //int n, k, T, i = 1, j;
    int n, k, T, i = 0, j;
    //int sum = 1, count = 1, num = 1;
    int sum = 0, count = 1, num = 1;
    scanf("%d %d %d", &n, &k, &T);

    //for(j = 1; j <= n; ++j)
    for(j = 0; j <= n; ++j)
    {
      if(i == T)
      {
            break;
      }

      //num += count;
      //count++;
      if(num > k)
      {
            //num = num + count - k;
            num = num - k;
      }


      //if(j == n)
      if(j == 0 || j == n)
      {
            sum += num;
            i++;
            //j = 1;
            j = 0;
      }

      num += count;
      count++;
    }

    printf("%d", sum);
    return 0;
}

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

#include <stdio.h>
int main()
{
    int n, k, T;
    long long sum = 1, t=1, a=1;
    scanf("%d%d%d", &n, &k, &T);
    int i;
    for(i = 1; i < T; ++i)
    {
      t = (((a+a+n-1)*n/2)+t)%k;
      sum += t;
      a += n;
    }
    printf("%lld\n", sum);
    return 0;
}

人造人 发表于 2021-3-19 21:06:38

#include <stdio.h>

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

巴巴鲁 发表于 2021-3-19 22:20:26

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

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

巴巴鲁 发表于 2021-3-19 22:23:26

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

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

巴巴鲁 发表于 2021-3-19 22:24:24

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

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

巴巴鲁 发表于 2021-3-19 22:24:58

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


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

人造人 发表于 2021-3-19 23:58:13

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

#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;
      }


      printf("%d\n", num);
      if(j == n)
      {
            printf("    %d\n", num);
            sum += num;
            i++;
            j = 1;
      }
    }

    printf("%d", sum);
    return 0;
}


3 13 3
2
4
7
    7
11
9
    9



#include <stdio.h>

int main(void)
{
    //int n, k, T, i = 1, j;
    int n, k, T, i = 0, j;
    //int sum = 1, count = 1, num = 1;
    int sum = 0, count = 1, num = 1;
    scanf("%d %d %d", &n, &k, &T);

    //for(j = 1; j <= n; ++j)
    for(j = 0; j <= n; ++j)
    {
      if(i == T)
      {
            break;
      }

      //num += count;
      //count++;
      if(num > k)
      {
            //num = num + count - k;
            num = num - k;
      }


      printf("%d\n", num);
      //if(j == n)
      if(j == 0 || j == n)
      {
            printf("    %d\n", num);
            sum += num;
            i++;
            //j = 1;
            j = 0;
      }

      num += count;
      count++;
    }

    printf("%d", sum);
    return 0;
}


3 13 3
1
    1
2
4
7
    7
11
3
9
    9

人造人 发表于 2021-3-20 00:05:20

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


#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;
}

4 14 4
57


#include <stdio.h>

int main(void)
{
    //int n, k, T, i = 1, j;
    int n, k, T, i = 0, j;
    //int sum = 1, count = 1, num = 1;
    int sum = 0, count = 1, num = 1;
    scanf("%d %d %d", &n, &k, &T);

    //for(j = 1; j <= n; ++j)
    for(j = 0; j <= n; ++j)
    {
      if(i == T)
      {
            break;
      }

      //num += count;
      //count++;
      if(num > k)
      {
            //num = num + count - k;
            num = num - k;
      }


      //if(j == n)
      if(j == 0 || j == n)
      {
            sum += num;
            i++;
            //j = 1;
            j = 0;
      }

      num += count;
      count++;
    }

    printf("%d", sum);
    return 0;
}

4 14 4
30


#include <stdio.h>
#define LL long long int

int main(void) {
      int i = 1;
      LL sum = 1, x, add = 1, n, k, t;
      scanf("%lld%lld%lld",&n,&k,&t);
      while (i < t) {
                x = add + ((i-1)*n + 1 + i*n)*n/2; // 得到这次这个人所报的数字

                i++;// 过这个人的次数加1
                x = x % k; //当大于k的部分需要返回
                sum += x; //数字和
                add = x; // 返回
      }
      printf("%lld",sum);
      return 0;
}

4 14 4
30

巴巴鲁 发表于 2021-3-20 13:02:11

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

啊，抱歉，我思路有问题

yayc_zcyd 发表于 2021-3-21 21:45:24

哈哈，你也要考蓝桥杯啊{:10_256:}

han125416866 发表于 2021-3-22 14:25:39

{:5_106:}

巴巴鲁 发表于 2021-3-23 12:28:54

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

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

yayc_zcyd 发表于 2021-3-23 19:14:24

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

必须的，但是我发现蓝桥杯考的几乎全是算法{:10_262:}

查看完整版本: 时间超时