Thuyền cứu người trong C ++

Giả sử chúng ta có một mảng được gọi là người. Bây giờ người thứ i có trọng lượng người [i], và mỗi thuyền có thể chở một trọng lượng giới hạn tối đa. Nếu mỗi thuyền chở nhiều nhất 2 người đồng thời với điều kiện là tổng khối lượng của những người đó nhiều nhất là giới hạn. Chúng ta phải tìm số thuyền tối thiểu để chở mỗi người đã cho. Vì vậy, nếu đầu vào là [3,2,1,2] và giới hạn là 3, thì chúng ta cần ba thuyền. [(1,2), (2), (3)].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp mảng người

• i:=0, j:=kích thước của mảng người - 1, ret:=0

• trong khi tôi <=j

  • nếu người [i] + người [j] <=giới hạn thì i:=i + 1 và j:=j - 1, ngược lại thì j:=j - 1

  • ret:=ret + 1

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[3,2,1,2]
3

Đầu ra

3