为什么我的代码在提交代码后出错

Question

在 CodeChef 网站 problem SQUIDRULE 中，它在提交后给了我一个运行时间错误，但是当我运行程序时，它给了我正确的答案运行成功了。

#include <stdio.h>

int main(void) {
    int T, s, a[1000], b[100];
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &s);

        for (int i = 1; i <= s; i++) {
            scanf("%d", &a[i]);
        }

        for (int i = 1; i <= s; i++) {
            int sum = 0, c;

            for (int j = 1; j <= s; j++) {
                sum = sum + a[j];
            }

            c = sum - a[i];
            b[i] = c;
        }

        for (int i = 1; i <=s; i++) {
            for (int j = i + 1; j <=s; j++) {
                if (b[i] > b[j]) {
                    int c;
                    c = b[i];
                    b[i] = a[j];
                    b[j] = c;
                }
            }
        }

        printf("%d\n",b[s]);
    }

    return 0;
}

Answer 1

来自我的热门评论...

在你的第二组嵌套 for 循环中，它需要 O(n^2) 时间，你正在排序 [使用慢冒泡排序而不是 qsort？]。最后，你只想打印 b[s].

AFAICT，您根本不需要排序。您只是在寻找数组的最大值，因此您可以在 O(n) 时间内计算出它。

此外，sum 在 i 的所有迭代中都是不变的。因此，您可以将 j 循环移动到第二个 i 之上，并且只计算一次。再一次，您可以将运行时间从 O(n^2) 减少到 O(n)

正如 WeatherVane 指出的那样，您 a.

中需要 [至少] 10,000 个条目

此外，您可以通过在 scanf 循环中执行此操作来消除用于计算 sum 的单独 for 循环。

这是重构后的版本：

#include <stdio.h>

#define AMAX    (100000 + 10)
int s, a[AMAX];
int sum;

int
fast(void)
{

    int mx = sum - a[0];

    for (int i = 1; i < s; i++) {
        int c = sum - a[i];
        if (c > mx)
            mx = c;
    }

    return mx;
}

int
main(void)
{

    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &s);

        sum = 0;
        for (int i = 0; i < s; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
        }

        int v2 = fast();
        printf("%d\n",v2);
    }

    return 0;
}

为什么我的代码在提交代码后出错

Why my code is giving error after i submit code

c

runtime-error