主題
題目連結：
題目意譯：
現在有 n 位工人。你被給定兩整數陣列 quality 和 wage，其中 quality[i] 為第 i 位工人的品質，而 wage[i] 為第 i 位工人預期的最小薪資。
我們想要聘請恰好 k 位工人來形成一個 paid group（似乎是專有名詞？本人見識淺薄，沒有見過這個詞而且也找不到對應中文。可能可以翻成「支薪群體」？）為了僱用 k 位工人，我們需要根據以下規則來為他們支薪：
這個 paid group 中的每一位工人必須至少支付他們所預期的最小薪資；
在這個 group 中，每一位工人的薪資必須與他們的品質成比例。這代表著如果 group 中有一位工人的品質是另一位工人的兩倍，則該工人應被支付另一位工人兩倍的薪資。
給定整數 k，回傳最少所需的金額來形成一個符合上述條件的 paid group。誤差範圍在 10 ^ (-5) 以內的答案也會視為是正確的。
限制：
n == quality.length == wage.length
1 ≦ k ≦ n ≦ 10 ^ 4
1 ≦ quality[i], wage[i] ≦ 10 ^ 4
範例測資：
範例 1：
輸入： quality = [10,20,5], wage = [70,50,30], k = 2
輸出： 105.00000
解釋： 我們對第 0 位工人支付 70，並對第 2 位工人支付 35。
範例 2：
輸入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
輸出： 30.66667
解釋： 我們對第 0 位工人支付 4，並對第 2 和 3 位工人支付 13.33333。
解題思維：
假設現在有 k 位工人的品質分別是 q1 、 q2 、 …… 、 qk，而最小預期薪資分別為 w1 、 w2 、 …… 、 wk。
我們可以看到要讓使所有工人被支付他們所期望的最小薪資且又要按照品質的比例來付，則其比例將會是所有 (wi / qi) 中最大者，其中 1 ≦ i ≦ k。當然，我們可以支付比這個比例大的薪資，但是只有這個比例才會得到支付這 k 個工人所需的最小薪資。
因此要支付這 k 位工人的最小且符合規則的薪資為 M × (q1 + q2 + …… + qk)，其中 M 為 max(w1 / q1, w2 / q2, ……, wk / qk)。
再假設現在有 k + 1 位工人的品質 q0 、 q1 、 …… 、 qk，而最小預期薪資分別為 w0 、 w1 、 …… 、 wk。
為了要把人數限制在 k 位，則我們需要把品質最大的工人移除掉。因為不論比例為何，最終的限制因素都只會是品質。
因此我們可以先把所有的工人按照「最小預期薪資除以品質」的比例由小排到大，並從小的開始選。一旦選到超過 k 個時就把品質最大的工人刪掉，因此這部份可以用一個優先佇列（Priority Queue）來解決。
然後只要每滿 k 個人計算當前所需的最小薪資，比例的話可以直接用當前看到的人之比例（即如果現在看到的工人有著最小預期薪資 wi 且品質為 qi，則直接用 wi / qi 即可），而不需要再用額外的優先佇列來維護最大的比例。原因如下：
假設 qi 不是品質最大者，則相安無事，本來就該用他的比例（因為有排序過了）。
而如果 qi 恰好是品質最大者。若如果此時我們「需要」前面的工人之比例才能得到更小的最小薪資，則代表著
M' × (q0 + q2 + …… + qk - qi) > M × (q0 + q2 + …… + qk - qi)
其中 M' 為先前的某個最大比例、 M 為 wi / qi，即當前比例。從上式可以推得
M' > M
由於我們已經按照比例由小排到大過，因此這是不可能發生的事。
總結以上兩種 qi 可能發生的狀況，我們必定還是可以得到最佳解。因此直接使用當前工人的比例即可。
而所有可能的「當前所需最小薪資」中的最小值即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
