Leetcode:857. Minimum cost of employing K workers [think in blocks + start with simplicity]

analysis

Suppose you choose k The individual is x1 … xk
They correspond to q and w yes q1…qk;w1…wk
The actual income is r1…rk;
We know ri = qi * t(t It's the proportional coefficient ）
Then there must be ri >= wi therefore t >= wi / qi
So the most greedy words t = max(wi / qi)
Special , We make t = [wage[i] / quality[i] for i in range(n)]
So we smoke k Come out alone
It is demand. sum(qi) * max(ti)
obviously max Easy to ask , We can t Make a sequence
Then when fixed max t after ,qi The scope is limited , In this case, use a sortedlist Before maintenance k Big ones can be done

ac code

from sortedcontainers import SortedList

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        #  Ratio of actual wages  =  The ratio of mass 
        #  Real wages  >=  Ideal salary 
        #  Minimum total salary 
        n = len(quality)
        t = [wage[i] / quality[i] for i in range(n)]

        #  from q,t choose k One makes  sum(qi) * max(ti)  Minimum , Multivariable use fixed one idea 
        # max(ti) Good fixation 
        # sum(qi) Choose the one in front k Make and minimize ,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

summary

Two quantity problems are hard to find
Fix one first , Then ask for another
Generally speaking , Fix the simple one first