解题思路
每一处最多用一张令牌,目标是让封堵和引流省下的水量尽量多,剩下暂缓的总和尽量小。把各点渗水量从大到小排序后贪心分配即可。
- 封堵能把一处残留清成 0,引流只能把一处变成 max(0,hi−g)。封堵省下的是整段 hi,引流省下的是 min(hi,g),所以封堵一定优先给渗水更大的点:若封堵给了小的、引流给了大的,把它们交换后总残留不会变差。
- 封堵用完以后,剩下的点里引流也优先给渗水更大的:min(h,g) 随 h 增大不会变小。
- 因此将 h 从大到小排序,前 u 处封堵(残留记 0),接着 v 处引流,其余暂缓,累加即答案。令牌用不完就丢掉。
- 渗水量和点数较大,求和时用 64 位整数。