[已解决]时间超时

巴巴鲁

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

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

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

跳转到最佳答案楼层

zip...

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

baige

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)

巴巴鲁

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

这是考的数学还是编程啊

baige

别的比赛数学更难

baige

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

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

人造人

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

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

愷龍

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

人造人

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

巴巴鲁

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
关键是超时，好像要是最高效的

#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

人造人

提问，为什么这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 00:05
提问，为什么这3个程序的输出不一样？

啊，抱歉，我思路有问题

yayc_zcyd

哈哈，你也要考蓝桥杯啊

han125416866

巴巴鲁

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

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

yayc_zcyd

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

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