练习1-P2672

Posted on Oct 20, 2025

贪心策略证明：

总疲劳值=选取的住户疲劳值之和+最远端路程疲劳值

按住户疲劳值排序，选前X的住户得到方案I

由最远端路程疲劳值的单调性知：最远端位置小于I的最远位置对应方案总疲劳值小于I的总疲劳值

那么疲劳值最大的选法，其最远端位置必然大于等于I的最远端位置。对于最远端位置大于I的选法，剩余的X-1个待选位置需最大化，即取住户疲劳值前X-1项，此时这些选法前X-1项固定，只需最后一项最大化，取

$$max(s[i]+2*d[i])$$

最后只需比较该取法和方案I，取疲劳值大的那个即可

PS：自然语言还是太啰嗦了，下次尝试用符号来刻画

上面最大化对应集合表述应是：

$$max\{S\}=max\{A \cap B\}=max\{A \cap \{max\{B\}\}\}$$

，即将子部分最大而化简整个方案集合（给这种靠感觉的变化打个正确性补丁）

在简化，抽象化的过程中，抛弃了题目的特殊性，导致方向错误

N种数列：$\{a_{i,n}\},1\le i \le N$ 不可能在$O(nlogn)$内求出

$$max\{\ \sum_{1\le i_1 \le ...i_N \le len} a_{sub \_ index(i),i_1} \}$$

这题的特殊性在于附加权的单调性，而不是数列的重复