資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚研究
法律研究用 C++ 拯救人們的船
假設我們有一個數組稱為 people。第 i 個人的體重為 people[i]，每艘船最多可以載重 limit。如果每艘船同時運送最多 2 人，只要這兩個人體重的總和不超過 limit 即可。我們必須找到運送每個人的最小船隻數。因此，如果輸入類似於 [3, 2, 1, 2]，而 limit 為 3，那麼我們需要三艘船。[(1, 2), (2), (3)]。
為了解決這個問題，我們將遵循以下步驟 -
對 people 陣列進行排序
i := 0，j := people 陣列的大小 - 1，ret := 0
只要 i <= j
如果 people[i] + people[j] <= limit，那麼將 i := i + 1 和 j := j - 1，否則將 j := j - 1
ret := ret + 1
返回 ret
讓我們看以下實現來更好地理解 -
範例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
sort(people.begin(), people.end());
int i = 0;
int j = people.size() - 1;
int ret = 0;
while(i <= j){
if(people[i] + people[j] <= limit){
i++, j--;
}else{
j--;
}
ret++;
}
return ret;
}
};
main(){
vector<int> v = {3,2,1,2};
Solution ob;
cout << (ob.numRescueBoats(v, 3));
}輸入
[3,2,1,2] 3
輸出
3
更新於： 30-04-2020
600 次觀看
廣告