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("%dn", max);
}
return 0;
}

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

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("%dn", max);
}
return 0;
}

没有循环应该更有效率。这个概念是代数解决问题，然后适当地舍入。

最大 k 的

t = N*k - k²*B

可以通过微分到 k 来找到：

k = N/(2*B)

这必须适当地四舍五入，然后插入到原始方程中

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

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

Answer 2

函数：printf()和函数：scanf()是非常"繁重的"，需要许多CPU周期。

强烈建议使用getchar_unlocked()和putchar_unlocked()，因为它们要快得多。

这里有两个比printf()快得多的 I/O 函数，scanf()注意使用size_t而不是int

#include <stdio.h>
void fastRead( size_t *a );
void fastWrite( size_t a );
inline void fastRead(size_t *a)
{
int c=0;
// note: 32 is space character
while (c<33) c=getchar_unlocked();
// initialize result value
*a=0;
// punctuation parens, etc are show stoppers
while (c>47 && c<58)
{
*a = (*a)*10 + (size_t)(c-48);
c=getchar_unlocked();
}
//printf( "%s, value: %lun", __func__, *a );
} // end function: fastRead

inline void fastWrite(size_t a)
{
char snum[20];
//printf( "%s, %lun", __func__, a );
int i=0;
do
{
// 48 is numeric character 0
snum[i++] = (char)((a%10)+(size_t)48);
a=a/10;
}while(a>0);
i=i-1; // correction for overincrement from prior 'while' loop
while(i>=0)
{
putchar_unlocked(snum[i--]);
}
putchar_unlocked('n');
} // end function: fastWrite