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%