একটি সংখ্যার তালিকা counts দেওয়া আছে যেখানে counts[i] = টাইপ i-এর আইটেম সংখ্যা। আরেকটি মান k দেওয়া আছে। আকার k গ্রুপ সর্বোচ্চ কতটি বানানো যাবে তা বের করতে হবে, শর্তে প্রতিটি গ্রুপে আলাদা টাইপের আইটেম থাকতে হবে।
উদাহরণ: counts = [2, 3, 5, 3], k = 2 হলে আউটপুট 6। চারটি টাইপ a,b,c,d। গ্রুপগুলো: [(c,a), (b,a), (c,b), (c,b), (d,a), (d,a)]।
সমাধানের পদ্ধতি
বাইনারি সার্চ + লালচী চেক (greedy check)।
possible(groups, k)ফাংশন:groupsসংখ্যক গ্রুপ বানানো সম্ভব কিনা চেক করুন।- প্রতিটি টাইপ
i-এর জন্য, সেটি অবদান রাখতে পারেmin(counts[i], groups)টি গ্রুপে (একই টাইপ এক গ্রুপে একবারই যেতে পারে)। - মোট প্রয়োজন
groups * k। সব টাইপের অবদান যোগ করুন, যদি ≥ প্রয়োজন হয় তবে সম্ভব। - বাইনারি সার্চ দিয়ে সর্বোচ্চ
groupsখুঁজে বের করুন।
পাইথন কোড
def possible(counts, groups, k):
required = groups * k
for i in range(len(counts)):
temp = min(counts[i], groups, required)
required -= temp
if required == 0:
return True
return False
def solve(counts, k):
res = 0
l = 0
r = sum(counts)
while l <= r:
m = l + (r - l) // 2
if possible(counts, m, k):
l = m + 1
res = max(res, m)
else:
r = m - 1
return res
# টেস্ট
counts = [2, 3, 5, 3]
k = 2
print(solve(counts, k)) # আউটপুট: 6সময় জটিলতা
O(n log S) - n = টাইপ সংখ্যা, S = sum(counts)। বাইনারি সার্চ O(log S), প্রতিটি চেক O(n)।
