Cheapest Fair Crew
Worker i does work of quality quality[i] and will not work for less than wage[i]. Hire exactly k workers under two rules:
- Pay is in proportion to quality: everyone hired gets the same amount per unit of quality.
- Nobody is paid less than their own lowest wage.
Return the least total pay, as a float.
Example 1
quality [4,2,6]
wage [8,10,6]
k 2
returns 20.0
Hire workers 0 and 2 at 2 per unit of quality: they get 8 and 12. Worker 1 would force everyone up to 5 per unit.
Example 2
quality [3,1]
wage [3,4]
k 1
returns 3.0
One worker is needed, and worker 0 asks for less.
Constraints
1 <= k <= len(quality) <= 200len(wage) == len(quality)1 <= quality[i], wage[i] <= 10**4
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.