c - 提高代码的速度效率

Question

// author- squeamishossifrage
#include <stdio.h>

int main() {
    int k, t, A, N, B, max, num_tests;
    scanf("%d", &num_tests);
    while (num_tests--) {
        scanf("%d %d", &N, &B);
        A = 1;
        k = N / B;
        for (k=N/B,max=0; k>0; k--) {
            t = (N-k*B) * k;
            if (t > max) max = t;
        }
        printf("%d\n", max);
    }
    return 0;
}

上面的代码(取自 this answer )似乎需要一秒多一点，但约束是在一秒内执行。我们如何在不使用多线程的情况下提高这类代码的速度(我不知道如何使用它们)？

Answer 1

这应该可以解决问题:

#include <stdio.h>

int main() {
    int k, N, B, max, num_tests;
    scanf("%d", &num_tests);
    while (num_tests--) {
        scanf("%d %d", &N, &B);
        k = (double)N / (2*B)+0.5;
        max = (N-k*B)*k;
        printf("%d\n", max);
    }
    return 0;
}

如果没有循环，应该会更有效率。这个概念是以代数方式解决问题，然后适本地舍入。

最大的k

t = N*k - k²*B

可以通过对k微分得到:

k = N/(2*B)

这必须适本地四舍五入，然后插入到原来的等式中

t = (N-k*B) * k;

那么这是正确的(最大)解决方案。