这里如果按照距离来考虑就太复杂了,于是转化对象,考虑客户
证明:
假设我们选的疲劳值最大的前X个的最远的一个的距离为 S 1 S_{1} S1,那么可以知道,一定不会存在一个更优的方案,使得这个方案的最远的距离比 S 1 S_{1} S1要小
所以更优的方案的最远的距离肯定要比 S 1 S_{1} S1大,假设我们选择了一个比 S 1 S_{1} S1远的,距离为 S 2 S_{2} S2的住户作为这个方案的最远的住户,我们直接考虑在这个情形下的最优状态是什么。肯定是选择 X − 1 X-1 X−1个住户,这些住户的距离小于 S 2 S_{2} S2,疲劳值尽可能大
那么肯定选择疲劳值前 X − 1 X-1 X−1大的住户,就是最开始的方案去掉疲劳值最小的住户
插一句,这一道题目在做的时候,我从样例感觉出来了一个结论,就是 X X X的决策一定包含 X − 1 X-1 X−1的决策,考虑多增加哪一个住户就可以了
从部分题解来看,这个想法也是正确的,但是不知道怎么证明
update 2024.7.21
哎,想到了转换对象,将客户排序了,但是没有想到这么做啊。。。