搜狐第二题，ac代码
转换成如下问题：k = ±1±2±3……±n，求给定k且等式有解的最小n，（代码利用了给定|k|<2w的条件）
先所有当加号处理，+变-在和上看相当于减了这个数的2倍
static int get(int k) {
k = Math.abs(k);
if (k > 20050)
return 0;
if (k <= 1)
return k;
int[] sum = new int[220];
for (int i = 0; i < 220; i++) {
sum[i] = i * (i + 1) / 2;
}
int bound = 0;
for (int i = 0; i < 220; i++) {
if ((sum[i] <= k) && (sum[i + 1] > k)) {
bound = i;
break;
}
}
if (sum[bound] == k)
return bound;
for (int i = 1; ; i++) {
if ((sum[bound + i] - k) % 2 == 0) {
return bound + i;
}
}
} 为什么sum[bound + i] - k)是偶数时一定能分解成前面数的和：可分奇偶数讨论，这里i一定小于4
查看45道真题和解析