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