主題
題目連結(jié)：
題目意譯：
你被給定兩整數(shù) n 和 k 以及兩個(gè)長(zhǎng)度為 n 的整數(shù)陣列 speed 和 efficiency ?，F(xiàn)在有著 n 位工程師編號(hào)為 1 到 n 。speed[i] 和 efficiency[i] 依序代表著第 i 位工程師的速度以及效率。
從 n 個(gè)工程師中選出最多 k 位不同的工程師來(lái)組成一支隊(duì)伍，其有著最大的工作效能。
一個(gè)隊(duì)伍的工作效能為這些工程師的速度總和，乘上它們所有人之中的最低效率值。
回傳這個(gè)隊(duì)伍最大的工作效能之值。因?yàn)榇鸢缚赡苁且粋€(gè)很大的數(shù)字，因此將其模 10 ^ 9 + 7 後回傳。
限制：
1 ≦ k ≦ n ≦ 10 ^ 5
speed.length == n
efficiency.length == n
1 ≦ speed[i] ≦ 10 ^ 5
1 ≦ efficiency[i] ≦ 10 ^ 8
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
輸出： 60
解釋：
我們能得到隊(duì)伍最大工作效能，藉由選擇工程師 2 （有著速度 = 10 和效率 = 4）以及工程師 5（有著速度 = 5 和效率 = 7） 。也就是說(shuō)，工作效能 = (10 + 5) × min(4, 7) = 60 。
範(fàn)例 2：
輸入： n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
輸出： 68
解釋：
此與第一個(gè)例子相同但 k = 3。我們可以選擇工程師 1 、工程師 2 、工程師 5 來(lái)得到隊(duì)伍的最大工作效能。也就是，工作效能 = (2 + 10 + 5) × min(5, 4, 7) = 68 。
範(fàn)例 3：
輸入： n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
輸出： 72
解題思維：
我們先將所有工程師按照他們的效率值由大排到小，並為此重新編號(hào)成新的 1 ～ n。因此我們可以看到每一位工程師 i ，都將是從最左側(cè)到他的位置（1 ～ i）所有工程師中效率值最低的人。
此時(shí)我們宣告一個(gè)優(yōu)先佇列 P（Priority Queue）來(lái)儲(chǔ)存目前選定的工程師之速度值，而速度越小的越接近頂端（因此 P.top() 為最小值）。
接著我們依序掃過(guò)每位工程師。當(dāng)遇到第 i 位工程師時(shí)，我們先判斷 P 的大小是否為 k 。如果是的話，我們需要先從中移除掉速度值最小的，即 P.top() 。然後再將第 i 位工程師的速度值推入 P 之中，代表我們現(xiàn)在要選擇他。
因此此時(shí)可以看到，此時(shí)的 P 之內(nèi)容即代表著在要選擇第 i 位工程師的情況下所能安排的最佳隊(duì)伍（我們選擇了 1 ～ i - 1 之中速度最大的 k - 1 個(gè)人（如果足 k - 1 的話））。因此此隊(duì)伍的工作效能為 P 中所有速度值總和 × 第 i 位工程師之效率值（因?yàn)楦鶕?jù)前面的排序，他將是這個(gè)隊(duì)伍效率最低的）。
如此一來(lái)，我們便知道了在必定選擇某位工程師的情況下，其隊(duì)伍所能得到的最大工作效能之值。
而在這所有工作效能之值中的最大值，即是整體的最大工作效能，即所求。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
