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

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



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

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