There are
N
workers. The i
-th worker has a quality[i]
and a minimum wage expectation wage[i]
.
Now we want to hire exactly
K
workers to form a paid group. When hiring a group of K workers, we must pay them according to the following rules:- Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
- Every worker in the paid group must be paid at least their minimum wage expectation.
Return the least amount of money needed to form a paid group satisfying the above conditions.
Example 1:
Input: quality = [10,20,5], wage = [70,50,30], K = 2 Output: 105.00000 Explanation: We pay 70 to 0-th worker and 35 to 2-th 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 0-th worker, 13.33333 to 2-th and 3-th workers seperately.
Note:
1 <= K <= N <= 10000
, whereN = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
- Answers within
10^-5
of the correct answer will be considered correct.
找合适的长度为k的subset。遍历整个array,每次找以[i]为baseline的符合条件的subset
O(NlogN)。注意double比较的写法。sort的时候要同时sort 3个array
class Solution { public double mincostToHireWorkers(int[] quality, int[] wage, int k) { int n = quality.length; Person[] person = new Person[n]; for (int i = 0; i < n; i++) { person[i] = new Person(quality[i], wage[i]); } Arrays.sort(person, (a, b) -> Double.compare(a.rate, b.rate)); PriorityQueue<Integer> que = new PriorityQueue<>((a, b) -> b - a); int sum = 0; for (int i = 0; i < k; i++) { que.add(person[i].quality); sum += person[i].quality; } double min = sum * person[k - 1].rate; for (int i = k; i < n; i++) { int max = que.poll(); que.add(person[i].quality); sum = sum - max + person[i].quality; min = Math.min(min, sum * person[i].rate); } return min; } class Person{ public int quality; public int wage; public double rate; public Person(int quality, int wage) { this.quality = quality; this.wage = wage; rate = wage * 1.0 / quality; } } }
No comments:
Post a Comment