题意
- 从i=1开始,到i=target,所需要的最小移动次数。
- 每次移动可以向左也可以向右
- 移动的距离遵守 1,2,3,4,5,…n
思路
- 向左移动x可以等效成向右移动-x,左右移动等效成向右移动适当加-号
- 分情况讨论
- 一直往右移动,刚好到达 target,此时次数最少为n
- 一直往右移动,超过target距离为d
d为偶数
即将d/2反向,即可到达target, 最少为 n+1。证明:d/2一定在[1, n]中。
显而易见:d 的最大值为,从n-1跳了n部,即 d = n-1(偶数) (n-1)/2,一定在[1, n]中。最小次数为 n
d为奇数
由于反向操作只能将 s 减少偶数,无法处理相距奇数的情况,必须多走一两步,将相距变为偶数,才能处理。 将一个数num反向,则造成的结果为sum-2*num
1.向往回走一步n+1,在往前走一步n+2,n+2-(n+1)=1, 此时d+1一定为偶数,回到上述情况。最小次数为n+2
2.往前继续走一步,n+1, 如果n+1+d<2n为偶数,则将[n+1+d]/2改为负数,最小次数为n+1
3.往前继续一步,n+1,如果 n+1+d<2n为奇数。则继续往前一步,n+1+d+n+2必为偶数,
n+2 <= (2n+3+d)/2 <= 1.5n+1,当d=1,和d=n-1时成立,最小次数为n+2
第1种情况和第3种情况是同一种情况。
图来至于灵茶灵神题解