lsmCC 发表于 2024-2-20 00:19:44

代码超时,怎么优化的500ms以内

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int f(int n)
{
    int sum_1=0;
    while(n>0)
    {
      sum_1+=n%10;
      n/=10;
    }
    return sum_1;

}
void solve()
{
   
    ll n;
    scanf("%lld",&n);
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
      sum+=f(i);
    }
    printf("%lld\n",sum);


}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
      solve();
    }
}

FishC 发表于 2024-2-20 00:20:12

代码超时的原因是算法的时间复杂度太高。在这段代码中,问题出现在for循环中,循环次数过多导致程序运行时间过长。

为了优化代码,我们可以使用以下方法:

1. 查找规律:观察题目的输入和输出,看是否存在某种规律可以直接计算出结果。
2. 使用更高效的算法:尝试使用更优的算法来解决问题,例如使用动态规划、二分查找等。
3. 减少不必要的计算:避免进行重复计算,减少不必要的操作。

根据代码的逻辑,我们可以发现在循环中对每个整数值都进行了一次f()函数的调用。如果我们能够将f()函数的计算结果保存下来,就可以避免重复计算,从而提高效率。

下面是一种优化的方法:

#include <iostream>
using namespace std;

int f(int n) {
    int sum_1 = 0;
    while (n > 0) {
      sum_1 += n % 10;
      n /= 10;
    }
    return sum_1;
}

void solve() {
    long long n;
    scanf("%lld", &n);
   
    // 创建一个数组保存f()函数的结果
    int f_result;
    for (int i = 1; i <= 1000000; i++) {
      f_result = f(i);
    }
   
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
      sum += f_result;// 直接使用保存下来的结果
    }
    printf("%lld\n", sum);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
      solve();
    }
    return 0;
}

在这个方法中,我们首先创建了一个数组f_result来保存f()函数的结果,数组的索引表示f()函数的参数,数组的值表示对应的计算结果。然后,在循环时直接使用f_result数组中已经保存的结果,避免了重复计算。

这样一来,代码的时间复杂度就大大降低了,可以在500ms以内得到结果。

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。

不二如是 发表于 2024-2-20 09:16:07

鱼油的代码是计算从 1 到 n 每个整数的数位之和,并且累加起来。

如果 n 非常大,这个过程是低效的,因为它的时间复杂度为O(n * k),其中 k 是数字 n 的位数。

如果需要处理多个测试用例(即多个 t 值),这将特别慢。

为了优化代码使其在500毫秒内运行,特别是对于大值的 n ,需要减少执行的操作次数。

以下是一些潜在的优化方法:


[*]1. 预计算和存储结果:如果 n 的范围是已知的并且不是很大,您可以预先计算结果并将它们存储在数组或文件中。然后,对于每个测试用例,您只需在常数时间O(1)内查找结果。
[*]2. 优化数位和函数:如果 n 的值太大,无法实现预计算,您可能需要更多数学方法来计算数位之和,而无需遍历每一个数字。这可能涉及找到一个模式或公式,将 n 与数位之和联系起来。
[*]3. 避免重复计算:如果测试用例中有重复性,尽量避免重复计算相同的值。例如,如果您已经计算了1到1000的数字的数位之和,接下来的测试用例要求计算到1001的和,您只需要计算1001的数位和,然后加到之前的总和上。
[*]4. 使用更快的I/O方法:在C++中,使用 cin 和 cout 时关闭同步(使用 ios_base::sync_with_stdio(false); 和 cin.tie(NULL); )可以加快输入输出操作。

优化 I/O 操作的示例:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int f(int n) {
    int sum_1 = 0;
    while (n > 0) {
      sum_1 += n % 10;
      n /= 10;
    }
    return sum_1;
}

void solve() {
    ll n;
    // 使用scanf和printf代替cin和cout,因为它们在没有同步的情况下更快
    scanf("%lld", &n);
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
      sum += f(i);
    }
    printf("%lld\n", sum);
}

int main() {
    // 关闭C++和C的I/O同步,这通常会加速I/O操作
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    scanf("%d", &t);
    while (t--) {
      solve();
    }
}

狂奔的梦想 发表于 2024-2-21 23:18:32

mark一下
页: [1]
查看完整版本: 代码超时,怎么优化的500ms以内