題目連結:
題目意譯:
你被給定一個陣列 people,其中 people[i] 為第 i 個人的重量,以及無限量的船,每艘船的最大承重為 limit。每艘船一次最多只能載兩個人,因此兩人之重量總和不應超過最大承重 limit。
回傳載走所有人最少所需船數。
限制:
1 ≦ people.length ≦ 5 × 10 ^ 4
1 ≦ people[i] ≦ limit ≦ 3 × 10 ^ 4
範例測資:
範例 1:
輸入: people = [1,2], limit = 3
輸出: 1
解釋: 1 艘船 (1, 2)
範例 2:
輸入: people = [3,2,2,1], limit = 3
輸出: 3
解釋: 3 艘船 (1, 2) 、 (2) 和 (3)
範例 3:
輸入: people = [3,5,3,4], limit = 5
輸出: 4
解釋: 4 艘船 (3) 、 (3) 、 (4) 、 (5)
解題思維:
其實跟
這題有幾分相似,只是現在在本題中我們不一定要每艘船都載著兩個人。
先排序後,最大跟最小重量的人配在同一艘船上、次大和次小重量同一艘……以此類推。
但是如果有一配對(例如說最大 + 最小)超過 limit 之最大承重,則代表著當前最大體重的人無法跟任何人在同一艘船上,再加上我們一定要把所有人載走。
因此此時順延體重較小的那一方(承前例,之後會變成次大配最小,如果又順延則變成第三大配最小),先把體重大的人載走。
完成以上過程之後,過程中用到的船數即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。