মান লেযিয়ে একটি people অ্যারে দেওয়া আছে। i-তম ব্যক্তির ওজন people[i], এবং প্রতিটি বোট সর্বোচ্চ limit ওजन বহন করতে পারে। প্রতিটি বোট সর্বোচ্চ ২ জন বহন করতে পারে, বশर्तে তাদের ওজনের যোগফল limit-এর চেয়ে কম বা সমান হয়। সব মানুষকে বহন করার জন্য ন্যূনতম বোট সংখ্যা খুঁজে বের করতে হবে। ইনপুট [3,2,1,2], limit = 3 হলে ৩টি বোট লাগবে। [(1,2), (2), (3)]।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
people অ্যারেটি সর্ট করুন
i := 0, j := people.size()-1, ret := 0
যখন i <= j
যদি people[i] + people[j] <= limit হয়, i++ এবং j--, অন্যথায় j--
ret++
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
