推 JIWP: 大師 04/03 23:11
推 ZooseWu: 大師 04/03 23:42
→ Mustafar: 這幾天每日都是以前出現過的二分搜 == 04/04 00:30
881. Boats to Save People
給定一個陣列Poople，People[i] 表示第 i 個人的重量，我們有無限艘船且每個船
最多只能負重 limit 的重量並且最多載兩個人，返回把所有人載走的最少所需船數。
Example :
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
思路：
1.因為船最多載兩個人，所以我們可以對重量貪婪，每次都讓重的人先上船，如果還可以
負重就讓最輕的人嘗試上船，這樣一來載完所有人就會是最少趟次。
2.因為要取最重和最輕的人所以我們可以先把people排序。
3.再來用雙指標表示當前要上船的人是誰，每次固定內縮右指標，如果可以負重就移動
左指標，每輪都讓趟次加一，當指標交錯時就是載完了。
Java Code：
-------------------------------------------
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int num = 0;
int l = 0;
int r = people.length - 1;
while (l <= r) {
if (people[l] + people[r] <= limit) {
l++;
}
r--;
num++;
}
return num;
}
}
-------------------------------------------
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680534650.A.476.html