समस्या विवरण
मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक मान k है। हम इस सूची को k गैर-खाली सबलिस्ट्स में विभाजित कर सकते हैं। हमें k सबलिस्ट्स के न्यूनतम सबसे बड़े योग को ढूंढना है।
उदाहरण के लिए, यदि इनपुट है nums = [2, 4, 3, 5, 12] और k = 2, तो आउटपुट 14 होगा, क्योंकि हम सूची को [2, 4, 3, 5] और [12] जैसे विभाजित कर सकते हैं।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम बाइनरी सर्च का उपयोग करेंगे:
- एक फंक्शन ok() परिभाषित करें जो ऐरे v, k, x लेता है
- cnt := 0, sum := 0
- v के प्रत्येक तत्व i के लिए:
- यदि sum + i > x, तो sum := i, cnt बढ़ाएं
- अन्यथा sum := sum + i
- यदि cnt ≤ k तो true वापस करें, अन्यथा false
- मुख्य विधि से:
- low := 0, ret := 0, high := 0
- nums के प्रत्येक तत्व i के लिए: high += i, ret += i, low := max(low, i)
- जब तक low ≤ high:
- mid := low + (high - low) / 2
- यदि ok(nums, k-1, mid) true है, तो ret := mid, high := mid - 1
- अन्यथा low := mid + 1
- ret वापस करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
bool ok(vector<int>& v, int k, int x) {
int cnt = 0;
int 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);
}
इनपुट
{2, 4, 3, 5, 12}, 2
आउटपुट
14