這也算一個(gè)數(shù)學(xué)類(lèi)的雜題吧。題目本身比較有意思，解題的思路很需要猜想。題目的意思用+和-去替代式子(? 1 ? 2 ? ... ? n = k)中
的？號(hào)，對(duì)于指定的K，求最小的n。
For example: to obtain k = 12 , - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。
這個(gè)題，我的思路大致如下。首先，K可能是正的也是負(fù)的，而且顯然負(fù)的情況，有相應(yīng)的正對(duì)應(yīng)情況。那么考慮所有k為正的情況。
由于k一定小于等于n*(n+1)/2的，所以可以先求出這樣的最小n。這個(gè)可以二分搜索，或者直接用解不等式方程(不過(guò)這種方法一直wa了)。
然后就剩下的是第二點(diǎn)了，假設(shè)a + b = n*(n+1)/2, a - b = k。可以得到
n*(n+1)/2 - k = 2 * b。意思是，必須滿足
n*(n+1)/2
和k的差為偶數(shù)。假如滿足了，這樣的n是不是一定OK了？？？
答案是肯定的，這一點(diǎn)就是需要猜想的地方了。因?yàn)椋屑?xì)觀察下，1到n的數(shù)字可以組合出任意的1到 n*(n+1)/4之間的數(shù)字，這個(gè)數(shù)字
即是b。至于證明，可以用數(shù)學(xué)歸納法從n==1開(kāi)始證明了。。。至此已經(jīng)很簡(jiǎn)單了。
由于求n存在2種不同的方法，而且我開(kāi)始用解一元二次不等式的方法求的N，出現(xiàn)了浮點(diǎn)誤差，一直WA了。后面改成二分才過(guò)了。。。
代碼如下：
#include <stdio.h>
#include <math.h>
int GetN(int nK)
{
int nBeg = 1;
int nEnd = sqrt(nK * 2) + 2;
while (nBeg <= nEnd)
{
int nMid = (nBeg + nEnd) / 2;
int nTemp = (nMid * nMid + nMid) / 2;
if (nTemp >= nK)
{
nEnd = nMid - 1;
}
else
{
nBeg = nMid + 1;
}
}
return nEnd + 1;
}
int main()
{
int nK;
int nTest;
scanf("%d", &nTest);
while (nTest--)
{
scanf("%d", &nK);
if (nK < 0)
{
nK *= -1;
}
//int nN = ceil(sqrt(2 * fabs(1.0 * nK) + 0.25) - 0.5 + 1e-9);
//上面那種方法存在浮點(diǎn)誤差,wa了三次
int nN = GetN(nK);
while (1)
{
if (((nN * nN + nN) / 2 - nK) % 2 == 0)
{
printf("%d\n", nN);
break;
}
++nN;
}
if (nTest)
{
printf("\n");
}
}
return 0;
}