C++로 사람을 구하는 보트

people이라는 배열이 있다고 가정합니다. 이제 i번째 사람은 사람[i]의 무게를 가지며 각 보트는 최대 무게를 실을 수 있습니다. 각 보트가 동시에 최대 2명을 태울 경우, 그 사람들의 무게의 합이 최대 한계인 경우에 한합니다. 우리는 주어진 모든 사람을 태울 수 있는 최소 보트 수를 찾아야 합니다. 따라서 입력이 [3,2,1,2]이고 제한이 3이면 3개의 보트가 필요합니다. [(1,2), (2), (3)].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 사람들 배열 정렬

• i :=0, j :=사람 배열의 크기 – 1, ret :=0

• 동안 나는 <=j

  • people[i] + people[j] <=limit이면 i :=i + 1이고 j :=j – 1이고, 그렇지 않으면 j :=j – 1

  • 렛 :=렛 + 1

• 리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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