leetcode：857. 雇佣 K 名工人的最低成本【分块思考 + 由简单入手】

分析

假设选了k个人是x1 … xk
他们对应的q和w是q1…qk;w1…wk
实际的收入是r1…rk;
我们知道ri = qi * t(t是比例系数）
然后必须有ri >= wi 因此t >= wi / qi
所以最贪心的话 t = max(wi / qi)
特别的，我们令t = [wage[i] / quality[i] for i in range(n)]
因此我们抽k个人出来
就是要求sum(qi) * max(ti)
显然max好求，我们可以对t排个序
然后当固定了max t之后，qi就被限制了范围，这样的话用个sortedlist维护前k大的即可搞定

ac code

from sortedcontainers import SortedList

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        # 实际工资之比 = 质量之比
        # 实际工资 >= 理想工资
        # 最小总工资
        n = len(quality)
        t = [wage[i] / quality[i] for i in range(n)]

        # 从q，t选k个使得 sum(qi) * max(ti) 最小,多变量使用固定一个的思想
        # max(ti)好固定
        # sum(qi)选前面的k个使得和最少,sortedlist?
        
        sorted_t_q = sorted([(tt, qq) for tt, qq in zip(t, quality)])
        #print(sorted_t_q)

        ans = inf
        stl = SortedList([])
        # init
        for i in range(k):
            stl.add(sorted_t_q[i][1])
        ans = min(ans, sum(stl[:k]) * sorted_t_q[k - 1][0])

        # next
        for i in range(k, n):
            stl.add(sorted_t_q[i][1])
            ans = min(ans, sum(stl[:k]) * sorted_t_q[i][0])



        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

总结

两个量的问题不好求
先固定一个，然后再求另一个
一般来说，先固定简单的那个