数据结构
网络
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 次观看
广告