思路:贪心+前缀和
对于第 i 个任务,设目标储存罐编号为 j(即 Qi),目标是将第 j 个储存罐装满,那么选择从第 k(k≤j) 个储存罐开始注入液体,那么 [k,j] 这些储存罐被装满的液体均来自从第 k 个储存罐溢出后流下的液体。
选择从第 k(k≤j) 个储存罐开始注入液体,则需要使得[k+1,j] 这些储存罐都注满,成本为 Pk×i=k∑j(Ci−Vi)。答案即
t=1minj(Pk×i=k∑j(Ci−Vi))
此外,代码中使用了一个 trick,就是对于每个任务,从 j 到 1 来枚举从每个储存罐开始注入液体(而不是从1到j),这样我们就可以维护这其中需要补充的液体量。因为如果是从 1 到 j 来枚举,则对于每次的需液量都需要 O(n) 去查询,导致总复杂度是O(n3) , 当然也可以直接使用前缀和来维护。