推 aioiwer318: 別卷了 05/04 15:55
推 argorok: 別卷了 05/04 15:57
推 wu10200512: 別卷了 05/04 16:01
推 digua: 大師 05/04 16:02
→ ChungHsi1021: 別卷了 05/04 16:04
推 sustainer123: 大師 05/04 16:38
881. Boats to Save People
有一個array people，people[i]代表這個人的重量
現在要用一艘船載所有人
船一次最多能兩個人，且最大負重為limit
請問最少幾次就能載完所有人
思路:
將people排序，用two pointer指向最重、最輕的人
每次一定會載走最重的那個
如果最重+最輕<limit，那就連最輕的也載走
就這樣載走所有人，就可以得到答案了
因為要排序所以時間複雜度是o(nlog(n))
換個想法，因為每個人的體重一定都是<=limit
那建立一個array長度為limit+1
去記錄每個體重出現的次數
這樣就只要o(n)就好
c code :
int numRescueBoats(int* people, int peopleSize, int limit) {
int *rec=(int *)calloc(limit+1,sizeof(int));
for (int i=0;i<peopleSize;i++){
rec[people[i]]++;
}
int r=limit,l=0,ans=0;
while(r>=l){
while(r>=l && rec[r]<=0){
r--;
}
while(r>=l && rec[l]<=0){
l++;
}
if (l>r){
break;
}
ans++;
rec[r]--;
if ((r+l)<=limit){
rec[l]--;
}
}
return ans;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.11.31 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714809260.A.F80.html