Minimum Cost To Hire Exactly K Workers
You hire exactly k workers from a pool. Two fairness rules: each worker is paid in proportion to their quality relative to others in the group, and every worker must receive at least their stated minimum wage. Minimize the total payroll.
Problem
Given quality[i] and wage[i] for n workers and an integer k, hire exactly k workers so that within the group (a) pay is proportional to quality, and (b) everyone earns at least their wage. Return the minimum total cost. Answers within 1e-5 of the true value are accepted.
Input
Arrays quality and wage of length n, and integer k.
Output
The minimum total payment as a floating-point number.
Constraints
- 1 ≤ k ≤ n ≤ 1e4
- 1 ≤ quality[i], wage[i] ≤ 1e4
Examples
Example 1
Input
quality=[10,20,5] wage=[70,50,30] k=2
Output
105.00000
Hire workers 0 and 2 at ratio 7: pay 70 + 35 = 105.
Example 2
Input
quality=[3,1,10,10,1] wage=[4,8,2,2,7] k=3
Output
30.66667
Optimal trio gives the minimum proportional payroll.