目的地最短步数
目的地最短步数
https://www.nowcoder.com/practice/24ec35c2a8054a7b831a5a3ea660d729?tpId=98&tqId=32875&tPage=3&rp=3&ru=%2Fta%2F2019test&qru=%2Fta%2F2019test%2Fquestion-ranking
题目难度：二星
考察点：归纳
方法：归纳、找规律
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;
}
投递小米集团等公司10个岗位