这是反悔贪心
下面证明只会反悔一次
假设我们选的疲劳值最大的前X个的最远的一个的距离为\(S_{1}\)，那么可以知道，一定不会存在一个更优的方案，使得这个方案的最远的距离比\(S_{1}\)要小
所以更优的方案的最远的距离肯定要比\(S_{1}\)大，假设我们选择了一个比\(S_{1}\)远的，距离为\(S_{2}\)的住户作为这个方案的最远的住户，我们直接考虑在这个情形下的最优状态是什么。肯定是选择\(X-1\)个住户，这些住户的距离小于\(S_{2}\)，疲劳值尽可能大
那么肯定选择疲劳值前\(X-1\)大的住户，就是最开始的方案去掉疲劳值最小的住户
所以只会反悔贪心一次
插一句，这一道题目在做的时候，我从样例感觉出来了一个结论，就是\(X\)的决策一定包含\(X-1\)的决策，考虑多增加哪一个住户就可以了
从部分题解来看，这个想法也是正确的，但是不知道怎么证明
标签：,方案,疲劳,距离,反悔,住户,最远 From： https://www.cnblogs.com/dingxingdi/p/17872464.html