# [LeetCode 857. Minimum Cost to Hire K Workers ( HARD ) ](https://leetcode.com/problems/minimum-cost-to-hire-k-workers/)

:::success
[相似題 : 1383. Maximum Performance of a Team](https://hackmd.io/BaUbRo4vTdi69qpEyTFvEg)
:::

>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.

:::info
**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.
:::

:::info
**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.
:::

:::warning
**Constraints:**
* 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.
:::

---

### Approach 1 : Max Heap ( Priority Queue ) :book:
**`32ms ( 87.22% )`** **`O()`**

* 根據 `Rule 1` 因為要讓被雇用的人獲得的薪水**比例相同**，所以希望**比例越小越好**，假設 **`ratio = wage / quality`**。
再根據 `Rule 2` 可以知道，`SumOfQuality` 也是**越小越好**，所以透過 `max_heap` 刪除最大的 `quality`。
* 將 **`ratio & quality`** 存入 **`pair`** 中，並將 `ratio` 的部分由小到大進行 **`sort`**。
* **`SumOfQuality`** 紀錄當前 `quality` 總和，**`ans`** 紀錄當前最小答案。
* 目標找出最少的花費 **`money = SumOfQuality * ratio[i]`**。 ( 因為 `ratio` 是由小到大排序，所以只須考慮 `SumOfQuality & ratio[i]`)。
* **`max_heap`** 儲存當前使用的 `quality`。
>* 每次都將 `quality` 放入 `heap` 中，**`SumOfQuality += quality[i]`**。
>* 當 `size > k` 時，**`SumOfQuality -= heap.top()`**，並 `pop top of the value`。
>* 當 `size == k` 時才能判斷 **`ans = min(ans, SumOfQuality * ratio[i])`**。
>( 因為需要**剛剛好雇用 `k` 個員工**，所以當 `size < k` 時就先判斷會錯誤 )。

---

>**EXAMPLE :**
>**`quality = [10, 20, 5]`、`wage = [70, 50, 30]`、`k = 2`**。
> ---> **`ratio = [7, 2.5, 6]`**。
> 1. **sort ratio** :
> ---> `r = [2.5, 6, 7]`。
> ---> `q = [20, 5, 10]`。
> 2. **Max Heap** :
> **`SumOfSpeed = 0`**、**`ans = 999999999`**。
>> * i = 0 ---> heap = `({2.5, 20})` ---> `size < k`。
>> **`SumOfQuality = 20`**、**`ans = 999999999`**。
>> * i = 1 ---> heap = `({2.5, 20}, {6, 5})`。
>> **`SumOfQuality = 25`**、**`money = 25 * 6 = 150`**、**`ans = 150`**。 :+1:
>> * i = 2 ---> heap = `({7, 10}, {6, 5})`。
>> **`SumOfQuality = 15`**、**`money = 15 * 7 = 105`**、**`ans = 105`**。 :+1:

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        vector<pair<double, int> > worker;  // ratio, quality
        
        for(int i=0; i<quality.size(); i++){
            worker.push_back({wage[i]*1.0/quality[i], quality[i]});
        }
        sort(worker.begin(), worker.end());
        
        // heap //
        priority_queue<int > heap;  // quality
        int SumOfQuality = 0;
        double ans = 999999999;
        for(int i=0; i<worker.size(); i++){
            SumOfQuality += worker[i].second;
            heap.push(worker[i].second);
            
            if(heap.size() > k){
                SumOfQuality -= heap.top();
                heap.pop();
            }
            if(heap.size() == k)    ans = min(ans, SumOfQuality * worker[i].first);  
        }
        
        return ans;
    }
};