您的位置:首页 > 文旅 > 旅游 > 免费素材网站pexels_网络设备维护是做什么的_百度客服联系方式_青岛做网络推广的公司有哪些

免费素材网站pexels_网络设备维护是做什么的_百度客服联系方式_青岛做网络推广的公司有哪些

2025/3/15 11:55:48 来源:https://blog.csdn.net/2301_79083000/article/details/146258113  浏览:    关键词:免费素材网站pexels_网络设备维护是做什么的_百度客服联系方式_青岛做网络推广的公司有哪些
免费素材网站pexels_网络设备维护是做什么的_百度客服联系方式_青岛做网络推广的公司有哪些

在这里插入图片描述
在这里插入图片描述
题意

  • 从i=1开始,到i=target,所需要的最小移动次数
  • 每次移动可以向左也可以向右
  • 移动的距离遵守 1,2,3,4,5,…n

思路

  • 向左移动x可以等效成向右移动-x,左右移动等效成向右移动适当加-号
  • 分情况讨论
  1. 一直往右移动,刚好到达 target,此时次数最少为n
  2. 一直往右移动,超过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种情况是同一种情况。
在这里插入图片描述
图来至于灵茶灵神题解

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com