ETH官方钱包

前往
大廳
主題

LeetCode - 881. Boats to Save People 解題心得

Not In My Back Yard | 2022-11-27 12:00:10 | 巴幣 0 | 人氣 209

題目連結:


題目意譯:
你被給定一個陣列 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 之最大承重,則代表著當前最大體重的人無法跟任何人在同一艘船上,再加上我們一定要把所有人載走。

因此此時順延體重較小的那一方(承前例,之後會變成次大配最小,如果又順延則變成第三大配最小),先把體重大的人載走。

完成以上過程之後,過程中用到的船數即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作