#857
Minimum Cost to Hire K Workers
expert · 1120 · lc hard +32 · failed · 63.6% accepted · 3,048 likes · top 66%
Description
There are n workers. You are given integer arrays quality and wage where quality[i] is the quality of worker i and wage[i] is their minimum acceptable pay.
To hire a group of exactly k workers, you must satisfy:
- Every hired worker is paid at least their minimum wage.
- Pay within the group is proportional to quality: a worker with double the quality of another must earn twice as much.
Given the integer k, return the minimum total cost to hire exactly k workers satisfying both rules. Answers within 10-5 of the true answer are accepted.
Example 1:
Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.
Example 2:
Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output: 30.66667
Explanation: We pay 4 to 0th worker, 13.33333 to 2nd and 3rd workers separately.
Code
1
2
3