问题分析

本题的目标是找到最小的自然数 $N$，使得在 $1$ 到 $N$ 这些自然数前添加正号或者负号后，它们的代数和能够等于给定的正整数 $S$。

核心思路

$1$. 计算总和：首先，考虑从 $1$ 到 $N$ 的所有自然数相加的和，根据等差数列求和公式，其总和 $sum$ 为 $sum=\frac{N\times(N + 1)}{2}$。例如，当 $N = 3$ 时，$sum = 1+2 + 3=\frac{3\times(3 + 1)}{2}=6$。 $2$. 符号改变的影响：当把 $1$ 到 $N$ 中某个数 $k$ 前面的符号从正号变为负号时，总和的变化量是 $2k$。这是因为原本是加 $k$，现在变成减 $k$，相当于总和减少了 $2k$。比如，若原本是 $1 + 2+3 = 6$，把 $2$ 前面的符号变为负号，就变成了 $1-2 + 3 = 2$，总和减少了 $2\times2 = 4$。由此可知，改变符号后总和的变化量一定是偶数。 $3$. 判断条件：要使得 $1$ 到 $N$ 这些数通过添加正负号后能得到和 $S$，那么 $sum - S$ 必须是非负偶数。因为 $sum$ 是所有数都取正号时的和，当我们改变某些数的符号后得到和 $S$，$sum - S$ 就是改变符号导致的总和变化量，而这个变化量必然是偶数，同时它不能是负数。

具体步骤

$1$. 初始化：令 $N$ 从 $1$ 开始，$N$ 代表当前考虑的最大自然数。 $2$. 计算总和：计算从 $1$ 到 $N$ 的所有自然数的和 $sum=\frac{N\times(N + 1)}{2}$。 $3$. 条件判断：检查 $sum - S$ 是否为非负偶数。如果满足 $(sum - S)\geq0$ 且 $(sum - S)\%2 == 0$，则说明找到了满足条件的最小 $N$，停止循环。 $4$. 递增 $N$：如果不满足条件，则将 $N$ 加 $1$，继续步骤 2 和步骤 3。

复杂度分析

• 时间复杂度：由于是从 $1$ 开始逐步增加 $N$，直到满足条件为止。因为 $sum=\frac{N\times(N + 1)}{2}$ 近似为 $\frac{N^2}{2}$，当 $sum\geq S$ 时停止循环，所以 $N$ 大约为 $\sqrt{2S}$，时间复杂度为 $O(\sqrt{S})$。
• 空间复杂度：整个过程只使用了常数级的额外变量，如 $N$、$sum$ 和 $S$，所以空间复杂度为 $O(1)$。

#include <iostream>

int main() {
    int S;
    std::cin >> S;

    int N = 1;
    while (true) {
        int sum = N * (N + 1) / 2;
        if ((sum - S) >= 0 && (sum - S) % 2 == 0) {
            break;
        }
        N++;
    }

    std::cout << N << std::endl;
    return 0;
}