মান লেযিয়ে Nটি ব্যানানা পাইল আছে, i-তম পাইল-এ piles[i] ব্যানানা। গার্ডরা গিয়ে H ঘণ্টা পর ফিরে আসবে। কোকো তার ব্যানানা-পার-আওয়ার খাওয়ার গতি K নির্ণয় করতে পারে। প্রতিটি ঘণ্টায়, সে একটি পাইল বেছে নিয়ে সেখান থেকে K ব্যানানা খায়। পাইল-এ K-র চেয়ে কম ব্যানানা থাকলে সে সেটি পুরো খায় এবং ওই ঘণ্টায় আর কিছু খায় না। কোকো ধীরে খেতে চায় কিন্তু গার্ড ফিরার আগে সব ব্যানানা খাওয়া শেষ করতে চায়। সে সব ব্যানানা H ঘণ্টায় খায় শেষ করতে পারেন এমন ন্যূনতম পূর্ণসংখ্যা K খুঁজে বের করতে হবে। ইনপুট [3,6,7,11], H = 8 হলে আউটপুট ৪।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
ok() নামে একটি মেথড সংজ্ঞায়িত করুন, যা অ্যারে a, x এবং h নেবে
time := 0
i = 0 থেকে a.size()-1 পর্যন্ত লুপ চালান
time := time + a[i] / x
যদি a[i] % x != 0 হয়, time++
time <= H হলে true রিটার্ন করুন
মেইন মেথড থেকে - n := piles.size(), low := 1, high := 0
i = 0 থেকে n-1 পর্যন্ত: high := max(piles[i], high)
যখন low < high
mid := low + (high - low) / 2
যদি ok(piles, mid, H) true হয়, high := mid, অন্যথায় low := mid + 1
high রিটার্ন করুন
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public: bool ok(vector <int>& a, int x, int H){ int time = 0; for(int i = 0; i < a.size(); i++){ time += a[i] / x; time += (a[i] % x ? 1 : 0); } return time <= H; } int minEatingSpeed(vector<int>& piles, int H) { int n = piles.size(); lli low = 1; lli sum = 0; lli high = 0; for(int i = 0; i < n; i++)high = max((lli)piles[i], high); while(low < high){ int mid = low + (high - low) / 2; if(ok(piles, mid, H)){ high = mid; }else{ low = mid + 1; } } return high; } }; main(){ vector<int> v = {3,6,7,11}; Solution ob; cout << (ob.minEatingSpeed(v, 8)); }ইনপুট
[3,6,7,11] 8
আউটপুট
4
