【每日一题】5月8日题目精讲 贪心

题号 NC14844
名称 codeJan与旅行
来源 Wannafly挑战赛7
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

这题中，我们不难证明，那么最后我们一定会在两个点直接徘徊或者直达某个点。
证明如下：
若不在两点间徘徊有最短距离，设我们走的点的序列为: (对于)
那么走的距离就是:
那么，对于其中的最小的那个来说
我们如果一直在和两个点间徘徊直到走的点的个数等于这个策略用的距离就是:
明显的这个距离是小于等于上面的距离的，与我们假设不符合，所以，我们最后一定是在两点间徘徊的（若k=t的话，就是直达某个点了）
所以，我们可以考虑枚举在哪两个点间徘徊，那么，我们只需要枚举在i和i+1两个点间徘徊就行了，计算也很简单，答案取最小即可
但是，我们提交上去后，wa了，为啥？
看hack数据。
我们发现，我们最佳是在10和14两点之间徘徊，但是，我们可以在一开始的时候，先从p走到1，再从1走到10，开始徘徊，这样，我们就可以少徘徊一次，而我们从p走到1再到p，只用了2步，而徘徊一次需要4步，所以，我们如果先到1再从1到p的话，可以少走2步！
其实，分析式子的话也可以发现策略的不足。
因为，我们的式子其实只保证了这部分的距离是最小的，然而，前面我们走的是否最小却不能保证。
所以，我们每次再尝试先从p走到附近的一个点，再走到我们枚举的徘徊点看看这种策略是否可以使得距离更小。
可能有人会问，如果我走到附近两个或多个点，再到p，是否可能距离更小？
答案是不会的，因为，如果你走到附近两个或多个点后距离比我们当前算的更小。（为了方便说明我们只弄两个点设为x,y）
那么当且仅当，我们从x到y的距离小于我们枚举的徘徊的两个点之间的距离（化下式子就可以得出，我懒得化了qwq）
于是乎，我们发现，当我们枚举在x和y两个点徘徊时，答案就比上面我们那个策略还优，所以，我们不需要枚举先走到附近两个及以上的点再跑到目标点徘徊。

感谢@ThinkofBlank同学提供的精彩题解~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目5月15日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴