একটি bloomDay অ্যারে এবং m, k মান দেওয়া আছে। mটি বুকে (bouquet) তৈরি করতে হবে। প্রতিটি বুকে-তে kটি সংলগ্ন ফুল লাগবে। i-তম ফুল bloomDay[i] দিনে ফুটে। প্রতিটি ফুল শুধু একটি বুকে-তে ব্যবহার করা যায়। mটি বুকে বানানোর জন্য ন্যূনতম কত দিন অপেক্ষা করতে হবে সেটি বের করতে হবে। অসম্ভব হলে -1 ফেরত দিন।
যেমন, bloomDay = [5,5,5,5,10,5,5], m = 2, k = 3 হলে আউটপুট ১০।
- ৫ দিন পর: [x,x,x,x,_,x,x] - শুধু একটা বুকে বানানো যায়।
- ১০ দিন পর: [x,x,x,x,x,x,x] - দুটা বুকে বানানো যায়।
সমাধানের ধাপসমূহ
- n := bloomDay-এর আকার
- যদি m * k > n হয়, তবে -1 ফেরত দিন।
- possible(x) ফাংশন সংজ্ঞায়িত করুন:
- count := 0, bouquets := 0
- bloomDay-এর প্রতিটি d এর জন্য:
- যদি d <= x হয়, তবে count বাড়ান। যদি count == k হয়, তবে bouquets বাড়ান এবং count := 0।
- অন্যথায় count := 0।
- bouquets >= m হলে true, অন্যথায় false ফেরত দিন।
- বাইনারি সার্চ: left := 0, right := max(bloomDay) + 1
- যখন left < right:
- mid := (left + right) // 2
- যদি possible(mid) হয়, তবে right := mid, অন্যথায় left := mid + 1
- যদি possible(left) হয়, তবে left ফেরত দিন, অন্যথায় left + 1 ফেরত দিন।
উদাহরণ
def solve(bloomDay, m, k):
n = len(bloomDay)
if m * k > n:
return -1
def possible(x):
count = 0
bouquets = 0
for d in bloomDay:
if d <= x:
count += 1
if count == k:
bouquets += 1
count = 0
else:
count = 0
return bouquets >= m
left, right = 0, max(bloomDay) + 1
while left < right:
mid = (left + right) // 2
if possible(mid):
right = mid
else:
left = mid + 1
if possible(left):
return left
else:
return left + 1
bloomDay = [5,5,5,5,10,5,5]
m = 2
k = 3
print(solve(bloomDay, m, k))
ইনপুট
[5,5,5,5,10,5,5], 2, 3
আউটপুট
10
