資訊專欄INFORMATION COLUMN
Problem
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, where N = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
Answers within 10^-5 of the correct answer will be considered correct.
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
int n = quality.length;
double[][] workers = new double[n][2];
for (int i = 0; i < n; i++) {
double ratio = (double) wage[i] / quality[i];
workers[i] = new double[]{ratio, (double) quality[i]};
}
Arrays.sort(workers, (a, b)->Double.compare(a[0], b[0]));
PriorityQueue pq = new PriorityQueue<>((a, b)->Double.compare(b, a));
double total = Double.MAX_VALUE, temp = 0;
for (double[] worker: workers) {
temp += worker[1];
pq.offer(worker[1]);
if (pq.size() > K) {
double maxQuality = pq.poll();
temp -= maxQuality;
}
if (pq.size() == K) {
double curTotal = temp*worker[0];
total = Math.min(total, curTotal);
}
}
return total;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/72540.html
摘要：動態(tài)規(guī)劃復(fù)雜度時間空間思路直到房子，其最小的涂色開銷是直到房子的最小涂色開銷，加上房子本身的涂色開銷。我們在原數(shù)組上修改，可以做到不用空間。代碼找出最小和次小的，最小的要記錄下標(biāo)，方便下一輪判斷 Paint House There are a row of n houses, each house can be painted with one of the three colors...
摘要：題目解答利用的思路，只不過把三種顏色換成了種顏色，所以是如何把它的復(fù)雜度降到那么就是如果將顏色的部分只掃一遍。參考的里只需要記錄下每個的最小的兩個顏色。 題目：There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house w...
摘要：同時你可以選擇從第階開始或者第一階開始。我們的目標(biāo)是找出你爬到最頂層所付出的最小的開銷。最低開銷是，從第階開始，只花費就可以到頂層。想法動態(tài)規(guī)劃問題。的長度應(yīng)該為數(shù)組長度加一，其中數(shù)組的最后一個元素的值就是本題的答案，最低開銷。 題目詳情 On a staircase, the i-th step has some non-negative cost cost[i] assigned ...
摘要：在原數(shù)組上動規(guī)，每一行對應(yīng)一個房子，每一個元素代表從第一行的房子到這一行的房子選擇這一種顏色所花的最小開銷。所以每個元素該元素的值上一行兩個與該元素不同列元素的值的較小者。不過這次要記錄三個變量本行最小值，本行第二小值，本行最小值下標(biāo)。 Paint House Problem There are a row of n houses, each house can be painted ...
閱讀 2564·2021-11-24 09:39
閱讀 3579·2019-08-30 15:53
閱讀 669·2019-08-29 15:15
閱讀 2972·2019-08-26 13:23
閱讀 3319·2019-08-26 10:48
閱讀 710·2019-08-26 10:31
閱讀 847·2019-08-26 10:30
閱讀 2425·2019-08-23 18:32
