多因素最值问题总结

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

一般多因素的最值问题都与排序相关，关键是按什么排序，能有更好的策略。

下面我总结一些我遇到的算法思路

0X00 单因素排序

1383. 最大的团队表现值

首先发现是一个多因素最值问题，尝试两个关键字排序。

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

from heapq import heappush, heappop

class 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 = 0

        for 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 时间）：

能量石	获得的能量（交换前）	获得的能量（交换后）
i	e[i] - t * l[i]	e[i] - (t + s[i+1]) * l[i]
i+1	e[i+1] - (t+s[i]) * l[i+1]	e[i+1] - t * l[i+1]

计算吃这两块石头获得的能量：

获得的能量（交换前）	获得的能量（交换后）
e[i] + e[i+1] - t * (l[i] + l[i+1]) - s[i] * l[i+1]	e[i] + e[i+1] - t * (l[i] + l[i+1]) - s[i+1] * l[i]

要想交换后的能量更高即：s[i+1] * l[i] < s[i] * l[i+1] => l[i+1] / s[i+1] > l[i] / s[i]

即我们的策略是：l[i] / s[i] 越大的先吃。

0X02 总结

对于多因素的最值问题，我们要做到的是：

• 判断题目是多因素最值问题
• 看能不能通过简单因素判断（常识）
• 通过交换两个相邻的，且交换后要比交换前要好，判断出我们到底应该用什么因素排序