P2672 [NOIP2015 普及组] 推销员

· · 个人记录

证明以下贪心策略是正确的

\max(\sum^{i}_{j = 1}val_j + \max^{i}_{j=1}(len_{j} \times 2), \sum^{i - 1}_{j = 1}val_j+\max_{j=i+1}^{n}(len_j \times 2 + val_j))

考虑在排完序的住户中选择前 X 个后对目前疲劳值的扩大。

下面的住户都是指排完序的住户。

如果存在更大的疲劳值选择方案，那么一定是后面某些点被选了，同时放弃了前面的某些点。

给出方案，唯一一种比选择前 X 个住户提供的疲惫值大的可能是放弃选择的住户中疲惫值最小的那一个，选择剩下的住户中（距离 \times 2 + 疲惫值，后面统称距离疲惫值）最大的那一个(后面统称 Y)。

核心代码

ans = max(sum[i] + per[i], sum[i - 1] + suf[i]); // sum[i] 是前i个住户的疲惫值的和，per[i] 是前i个住户的最大距离，suf[i] 是后面的住户的（距离疲惫值）最大值。

证明：

  1. 在只换一个的情况下，由于都固定放弃疲惫值最小的这个，总疲惫值减少的值是一定的，加上剩下中最大的值一定比加上其他值更优。当然，得出的新疲惫值是强制把新选择的住户的距离当做最远距离。

    如果新选择的住户的距离不是去掉第 X 个住户后的最远距离，那么有前 X 个住户中选择出的最远距离大于这个住户的距离，并且前 X 个住户的疲惫值都大于这个住户的疲惫值，那么这种选择一定劣于选择前 X 个住户，在统计答案的时候不会统计上。

  2. 如果选择继续尝试扩大，那么假设放弃了第 X - 1 个住户，选择了第 Z 个住户，首先 Z 的距离疲惫值小于 Y。如果 Z 的距离小于 Y，那么 Z 的距离不能贡献价值，因此 Z 的距离疲惫值就更小于 Y，所以不优。如果 Z 的距离大于 Y，那么现在选中 Z 后的总疲惫值就是

    \sum_{j = 1}^{X - 2} val_j + val_{Y} + val_{Z} + len_Z \times 2

    显然不选 Y 选上第 X - 1 个住户更优，因为 val_{x-1}>val_{Y}，此时价值又是

    \sum_{j = 1}^{X - 1} val_j + val_{Z} + len_Z \times 2

    因为

    val_{Z} + len_Z \times 2 < val_{Y} + len_Y \times 2

  3. 如果第一次扩大的时候不选距离疲惫值最大的住户，那么到第二次扩大时的情况等效于上一条所述。

综上，这种贪心策略才是正确的。单是题解区没有完整的证明，要不不证明，要不只证明浅显的一部分。

时间复杂度严格 O(n) 只需要基数排序即可。

我的代码-目前最优解