C++中救人的小船

假设我们有一个叫做people的数组。现在，第i个人的体重为[i]，每条船可以承受的最大重量为极限。如果每条船最多可同时容纳2个人，则这些人的重量总和最大为上限。我们必须找到载有每个特定人员的最少船只数量。因此，如果输入为[3,2,1,2]，且限制为3，则我们需要三艘船。[（1,2,,(2)，(3)]。

为了解决这个问题，我们将遵循以下步骤-

对人员数组进行排序

i：=0，j：=人数组的大小–1，ret：=0

当我<=j

如果people[i]+people[j]<=极限，则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