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

首先找到前n项和S刚好比k大的位置，然后判断和S与k的差值，如果是偶数及ok（因为此时可以通过改变前n项中某一个数字x的符号，使得和S减少2x，从而等于k），如果是奇数，n增大直到差为偶数。

 

注意k=0这种边界情况，此时应该输出n=3 (因为题目中n>=1)。

 

 

/*
 * uva10025.cpp
 *
 *  Created on: 2013-4-17
 *      Author: kevinjiang
 */
#include<cstdio>
#include<cmath>

int main() {

	int cases;
	int n;
	int k;
	scanf("%d", &cases);

	while (cases--) {
		scanf("%d", &k);
		if (k < 0)
			k = -k;
		n = (int) sqrt(2 * k) - 1;
		if(n<1)
			n=1;
		for (; (n * (n + 1) / 2 < k) || ((n * (n + 1) / 2 - k) % 2 == 1); n++) {
		}
		printf("%d\n", n);

		if (cases)
			printf("\n");
	}

	return 0;
}