সমস্যা বিবরণ
একটি সংখ্যার তালিকা nums এবং একটি মান k দেওয়া আছে। লিস্টটিকে kটি খালি নন সাবলিস্টে ভাগ করতে হবে। লক্ষ্য হলো এই kটি সাবলিস্টের মধ্যে সর্বাধিক যোগফল যেন ন্যূনতম হয়।
উদাহরণ: nums = [2, 4, 3, 5, 12], k = 2 হলে আউটপুট 14। কারণ [2, 4, 3, 5] (যোগফল ১৪) এবং [12] (যোগফল ১২) — সর্বাধিক যোগফল ১৪।
সমাধানের পদ্ধতি
বাইনারি সার্চ এবং গ্রিডি পদ্ধতি ব্যবহার করা হয়:
ok(v, k, x)ফাংশন: চেক করে যে কিxম্যাক্সিমাম সাবলিস্ট সাম umož্য করেkটি সাবলিস্টে ভাগ করা যায়।low = max(nums),high = sum(nums)সেট করুন।- বাইনারি সার্চ চালান:
mid = (low + high) / 2। - যদি
ok(nums, k-1, mid)সত্য হয়, তবেhigh = mid - 1, অন্যথায়low = mid + 1। - সর্বনিম্ন সম্ভাব্য
midরিটার্ন করুন।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
bool ok(vector<int>& v, int k, int x) {
int cnt = 0, sum = 0;
for (int i : v) {
if (sum + i > x) {
sum = i;
cnt++;
} else {
sum += i;
}
}
return cnt <= k;
}
int solve(vector<int>& nums, int k) {
int low = 0, ret = 0, high = 0;
for (int i : nums) {
high += i;
ret += i;
low = max(low, i);
}
while (low <= high) {
int mid = low + (high - low) / 2;
if (ok(nums, k - 1, mid)) {
ret = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ret;
}
int main() {
vector<int> v = {2, 4, 3, 5, 12};
int k = 2;
cout << solve(v, k);
return 0;
}
ইনপুট ও আউটপুট
ইনপুট: {2, 4, 3, 5, 12}, 2
আউটপুট: 14
