多因素最值问题总结多因素最值问题总结

前言：这个标题是我自己取的，我们要找到一个最值，而这个值与多种因素有关，所以我把他叫做「多因素最值问题」

一般多因素的最值问题都与排序相关，关键是按什么排序，能有更好的策略。
下面我总结一些我遇到的算法思路
0X00 单因素排序
1383. 最大的团队表现值
首先发现是一个多因素最值问题，尝试两个关键字排序。

如果按照 speed 排序，不好做，没思路，放弃
如果按照 efficiency 排序，就可以建立一个最多 k 大小的堆，固定 e 去遍历所有的方案这样的时间复杂度是 O(nlogn)

from heapq import heappush, heappopclass Solution: def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int: mod = 10 ** 9 + 7 res, minHeap, m = 0, [], [(v1, v2) for v1, v2 in zip(efficiency, speed)] m.sort(reverse=True) # print(m) sums = 0for e, s in m: heappush(minHeap, s) sums += s if len(minHeap) > k: sums -= heappop(minHeap) res = max(res, e * sums)return res % mod

这里有个比较坑的地方，就是如果是比较的话，中间计算过程是不能取余数的。
0X01 组合因素排序
125. 耍杂技的牛
跟上题一样同样是双因素最值问题，但是这题的最优策略不能按照单因素去排序，而是将这两个因素去组合。设一头牛 i 的重量是 w[i]，强壮程度是 s[i]。
这种题你没做过是想不出来的。
所以要把这种题当成「模板题」。
首先，按照经验来看这里的「最大风险值」的计算方法不涉及 * / 在构造的时候就不用选择 * /。
我们构造按照 w[i] + s[i] 从小到大的排序的方法（按照感觉来想也是这样，重量越大，越强壮的牛放在越后面），构造牛的序列，即 w[i] + s[i] 越小的放在前面。
现在通过「微扰法」证明：
假设有这么两头牛 w[i] + s[i] > w[i+1] + s[i+1]。第 i 头牛放在了上面，假设第 i 头牛上面的重量是 w_all，那么对于这两头牛来说，我们可以列出一个表：

牛	风险
i	w_all - s[i]
i+1	w_all + w[i] - s[i+1]

「微扰法」的核心就是交换，不影响其他的值。于是我们将两者交换，得出一张新表

牛	风险（交换前）	风险（交换后）
i	w_all - s[i]	w_all + w[i+1] - s[i]
i+1	w_all + w[i] - s[i+1]	w_all - s[i+1]

这个题要我们求的是使最大风险值最小，现在证明交换后的最大风险值会减小：
由于 w_all + w[i] - s[i+1] > w_all - s[i] 所以交换前的最大风险值是 w_all + w[i] - s[i+1] 并且 w_all + w[i] - s[i+1] > w_all - s[i+1] 以及 w_all + w[i] - s[i+1] > w_all + w[i+1] - s[i]
所以交换后的最大风险值一定是降低的，故牛从上到下的排序一定是按 w[i] + s[i] 的升序排序的。
我们再说一个难题，谷歌 2019 年 B 轮的题目：
【多因素最值问题总结】734. 能量石
这里有三个因素，s[i] 吃完能量石的时间, e[i] 能量石最初的能量, l[i] 能量石每秒消耗的能量。有了前一题的基础我们知道，这是一道「多因素最值问题」，和三个因素有关。
不能直接给出策略，但是我们可以来算一算（已过去 t 时间）：