C++で人々を救うためのボート

peopleという配列があるとします。これで、i番目の人の体重は人[i]になり、各ボートは最大重量の制限を運ぶことができます。各ボートが同時に最大2人を乗せる場合、それらの人の体重の合計が最大で制限されていることを条件とします。私たちは、与えられたすべての人を運ぶためのボートの最小数を見つけなければなりません。したがって、入力が[3,2,1,2]のようで、制限が3の場合、3つのボートが必要です。 [（1,2）、（2）、（3）]。

これを解決するには、次の手順に従います-

• 人々の配列を並べ替える

• i：=0、j：=人の配列のサイズ– 1、ret：=0

• i <=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