題目連結:
題目意譯:
一個公司計畫著要面試 2n 個人。給定陣列 costs,其中 costs[i] = [aCosti, bCosti],代表著第 i 個人飛到城市 a 所需的成本為 aCosti 以及飛到城市 b 所需的成本為 bCosti。
回傳將每個城市恰好安排了 n 個人飛過去最少所需的成本。
限制:
2 × n == costs.length
2 ≦ costs.length ≦ 100
costs.length 為偶數。
1 ≦ aCosti, bCosti ≦ 1000
範例測資:
範例 1:
輸入: costs = [[10,20],[30,200],[400,50],[30,20]]
輸出: 110
解釋:
第一個人飛到城市 a,其成本為 10。
第二個人飛到城市 a,其成本為 30。
第三個人飛到城市 b,其成本為 50。
第四個人飛到城市 b,其成本為 20。
因此使各自恰好一半的人面試於每個城市,總計最少所需成本為 10 + 30 + 50 + 20 = 110。
範例 2:
輸入: costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
輸出: 1859
範例 3:
輸入: costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
輸出: 3086
解題思維:
現在有兩個人,第一個人(以下稱 X)的成本各自為 a1 和 b1;第二個人(以下稱 Y)的成本則各為 a2 和 b2。
如果 X 飛到城市 a 、Y 飛到城市 b,則成本為
a1 + b2
而如果 X 飛到城市 a 、Y 飛到城市 b,則成本為
b1 + a2
因此單就這兩人來說:
如果 a1 + b2 < b1 + a2 的話,則應採取第一個選擇比較好;
而如果 a1 + b2 > b1 + a2 的話,則應採取第二個選擇比較好;
又如果 a1 + b2 == b1 + a2 的話,則兩者皆可。
因此如果我們用「a1 + b2 < b1 + a2」這個條件作為自定義排序之依據去將 nums 進行排序。排完之後 nums[0] 將會是必定飛向城市 a 的人、nums[2n - 1] 將會是飛向城市 b 的人。
將這兩人忽略掉之後剩下的 2n - 2 個人依舊滿足「第一人去城市 a、最後一人去城市 b」(因為排序的條件),便可以此類推出 nums 排序後前 n 個人是去城市 a、後 n 個人則是去城市 b。而這個成本將會是最低的(整體想法類似於
這題)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。