题目难度：二星
考察点：归纳

方法：归纳、找规律

1.分析：

这个题目其实就是相当于在1, 2, 3, 4....n中加正负号得到一个目标target，不需要BFS，我们可以采用贪心归纳的方法，因为我们要尽可能向右移动到达目的地，我们假设1+2+3+...+k=sum。那么就有如下两种情况：
(1). 如果sum=target，那么显然k就是我们要求的答案。
(2). 如果sum>target，那么sum-target就又存在两种情况：
a.sum-target是偶数，其实我们可以翻转其中某个数字的符号就可以变成target了。举个例子，假设sum-target=6，那么我们只需要把3变成-3，那么此时显然sum减小了6，所以就能得到target了，即1+2+...-（sum-target）/2+...+k=target，所以此时答案为k。
b. sum-target是奇数，那么sum-(target-1)就变成了一个偶数，所以类似上面的证明举个例子，假设sum-target=5，那么我们只需要将3变成-3，就可以得到target-1了，即1+2+...-（sum-target+1）/2+...+k=target-1。
此时我们在上述情况的基础上来考虑一下k的奇偶性，显然有两种情况：
(b.1) k是偶数，且满足k >sum-target+1，那么就有1+2+...-(sum-target+1)/2+....-(k/2)...+k+(k+1)=sum+(k+1)-sum+target-1-k=target，那么显然此时答案为k+1，
(b.2) k是奇数，同理可得1+2+...-(sum-target+1)/2.....+k-(k+1)+(k+2)=sum-(sum-target+1)+1=target，此时答案为k+2。
所以综上所述，他必能走到目的地，不存在走不到的情况。

算法实现：
(1). 输入n。
(2). 按照上述的推理判断情况。
(3). 根据判断的几种情况，输出结果ans。

2.复杂度分析：

时间复杂度：O(sqrt(n)) 
空间复杂度：O(1)

3.代码： 

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; cin>>n;
    int ans = 0, sum = 0;
    while(sum < n) {
        ans++;
        sum += ans;
    }
    sum -= n;
    if(sum & 1) {
        if(ans & 1) cout<<ans+2<<endl;
        else cout<<ans+1<<endl;
    }
    else cout<<ans<<endl;
    return 0;
}