這也算一個數(shù)學類的雜題吧。題目本身比較有意思，解題的思路很需要猜想。題目的意思用+和-去替代式子(? 1 ? 2 ? ... ? n = k)中
的？號，對于指定的K，求最小的n。
For example: to obtain k = 12 , - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。
這個題，我的思路大致如下。首先，K可能是正的也是負的，而且顯然負的情況，有相應的正對應情況。那么考慮所有k為正的情況。
由于k一定小于等于n*(n+1)/2的，所以可以先求出這樣的最小n。這個可以二分搜索，或者直接用解不等式方程(不過這種方法一直wa了)。
然后就剩下的是第二點了，假設a + b = n*(n+1)/2, a - b = k。可以得到
n*(n+1)/2 - k = 2 * b。意思是，必須滿足
n*(n+1)/2
和k的差為偶數(shù)。假如滿足了，這樣的n是不是一定OK了？？？
答案是肯定的，這一點就是需要猜想的地方了。因為，仔細觀察下，1到n的數(shù)字可以組合出任意的1到 n*(n+1)/4之間的數(shù)字，這個數(shù)字
即是b。至于證明，可以用數(shù)學歸納法從n==1開始證明了。。。至此已經(jīng)很簡單了。
由于求n存在2種不同的方法，而且我開始用解一元二次不等式的方法求的N，出現(xiàn)了浮點誤差，一直WA了。后面改成二分才過了。。。
代碼如下：
#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);
//上面那種方法存在浮點誤差,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;
}