超时了,请教各位大佬该怎么办

P2669 [NOIP2015 普及组] 金币

Kelly_1 @ 2023-12-18 11:07:02

#include<stdio.h>
int main()
{
    int k = 0;
    scanf("%d", &k);
    int pay = 0;
    int i = 1, j = 0;
    int a = 0, b = 0;
    for (i = 1;;i++)
    {
        ++a;
        for (j = 1;j <= i;j++)
        {
            pay += a;
            b++;
        }
        if (b == k)
        {
            break;
        }
    }
    printf("%d\n", pay);
    return 0;
}

这个超时了,请教各位大佬该怎么办


by JiaDu_Yin @ 2023-12-18 11:47:33

模拟思路太粗暴了,把计算过的天数和总天数相比,再借用乘法代替加法会优化一点


by JiaDu_Yin @ 2023-12-18 11:51:59

@Kelly_1 比如第n-K n天你这要运行(K-1)*n个加法循环,我判断计算过的天数+n也小于总天数,直接加(K-1)*n\n就好了


by Kelly_1 @ 2023-12-20 08:55:01

@JiaDu_Yin 谢谢,已经解决了。


|