LeetCode-搶救演算法大作戰#71
題目傳送門
Tag: Greedy題意
給你一個2維數字陣列costs
costs[i][0]表示i員工去A城市要花的時間
costs[i][1]表示i員工去B城市要花的時間
全部i個員工，限制去A, B兩城市的員工數要相同。(一半去A, 另一半去B)
請問要花的最小時間數是多少
想法
嗯，這題不是程式不會寫，是連自己手算都不會算QQ
看tag是greedy，想了一些時間，沒想出為什麼是greey…又不是都選a最小就好了囧
那我猜是dynamicProgram，想了一些時間，也不覺得是dynamicProgram啊…我又不能保證當下最佳解就會是未來最佳解囧，因為去A, B兩個city的人數要一樣啊囧
偷看
主要是偷看別人的想法，這題是卡在題目雖然有看懂，但完全不會解QQ
大概想法是，去算A, B兩城市的差值，這樣就知道去A比較省時，還是B比較省時。
如果差值為正(B-A > 0)，代表去A比較省時間；
如果差值為負(B-A <0 )，代表去B比較省時間。
接下來我再算「全部去B的時間」，再去扣掉A比較省的差值就好了
Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110化為表格後的結果，C欄代表B扣A的時間
數字為正，代表去A比較省時，且省了__的時間
以C[2]為例，代表去A比較好，A比B省了10個時間
D[6]代表的是如果員工全都去B，所需要的時間
題目限制A, B兩者的人數需各半，所以有一半的人要改去A
全部有4個人，兩個人需要改去A公司，由C欄可知，C[2]跟C[3]表明去A是比較省的，分別省10與170個時間。
所以再290 - 10 - 170即為答案110。
好了哦，學會手算了3口3，接下來就是寫程式了。
大意就是sum[B]、算b-a的差值、排序差值，取前半段相減就是了。
第9行，sort結果是由小到大。
所以第11行是從中間開始走完，而不是從頭走一半。
嗯嗯，這樣的確是greedy，取差值最大。
開獎
Runtime: 36 ms, faster than 82.52%
Memory Usage: 12.9 MB, less than 100.00%
