uva 10025 - The ? 1 ? 2 ? ... ? n = k problem

这也算一个数学类的杂题吧。题目本身比较有意思,解题的思路很需要猜想。题目的意思用+和-去替代式子(? 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的差为偶数。假如满足了,这样的n是不是一定OK了???
答案是肯定的,这一点就是需要猜想的地方了。因为,仔细观察下,1到n的数字可以组合出任意的1到 n*(n+1)/4之间的数字,这个数字即是b。至于证明,可以用数学归纳法从n==1开始证明了。。。至此已经很简单了。
由于求n存在2种不同的方法,而且我开始用解一元二次不等式的方法求的N,出现了浮点误差,一直WA了。后面改成二分才过了。。。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}