সি++-এ মানুষ বাঁচানোর জন্য নৌকা

ধরুন আমরা একটি অ্যারে আছে মানুষ নামক. এখন i-th ব্যক্তির ওজন আছে [i], এবং প্রতিটি নৌকা সীমার সর্বোচ্চ ওজন বহন করতে পারে। যদি প্রতিটি নৌকা একই সময়ে সর্বাধিক 2 জন লোক বহন করে, তবে সেই লোকদের ওজনের যোগফল সর্বাধিক সীমাতে থাকে। প্রতিটি প্রদত্ত ব্যক্তিকে বহন করার জন্য আমাদের ন্যূনতম সংখ্যক নৌকা খুঁজে বের করতে হবে। সুতরাং যদি ইনপুট হয় [3,2,1,2] এর মত, এবং সীমা 3 হয়, তাহলে আমাদের তিনটি নৌকা দরকার। [(1,2), (2), (3)]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• মানুষের অ্যারে সাজান

• i :=0, j :=মানুষের অ্যারের আকার – 1, ret :=0

• যখন আমি <=j

  • যদি মানুষ[i] + মানুষ [j] <=সীমা, তাহলে i :=i + 1 এবং j :=j – 1, অন্যথায় j :=j – 1

  • ret :=ret + 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