मान लीजिए हमारे पास एक चॉकलेट बार है जिसमें कुछ चंक्स हैं। प्रत्येक चंक में उसकी अपनी मिठास होती है जो sweetness नामक सूची द्वारा दी जाती है। यदि हम चॉकलेट को K दोस्तों के बीच बांटना चाहते हैं तो हम चॉकलेट बार को K कट्स का उपयोग करके K+1 टुकड़ों में काटना शुरू करते हैं, अब प्रत्येक टुकड़े में कुछ लगातार चंक्स होते हैं। यदि हम न्यूनतम कुल मिठास वाले टुकड़े को निकाल लेते हैं और अन्य टुकड़ों को अपने दोस्तों को दे देते हैं। हमें चॉकलेट बार को इष्टतम रूप से काटकर प्राप्त होने वाले टुकड़े की अधिकतम कुल मिठास ज्ञात करनी है।
तो, यदि इनपुट sweetness = [1,2,3,4,5,6,7,8,9], K = 5 है, तो आउटपुट 6 होगा क्योंकि आप चॉकलेट को [1,2,3], [4,5], [6], [7], [8], [9] इन टुकड़ों में विभाजित कर सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
एक फ़ंक्शन ok() परिभाषित करें, जो एक ऐरे v, कट्स, maxVal लेगा,
काउंटर := 0, टेम्प := 0
i := 0 से शुरू करें, जब i <= v का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
यदि टेम्प >= maxVal, तो:
(काउंटर को 1 से बढ़ाएं)
टेम्प := 0
यदि i, v के आकार के समान है, तो:
लूप से बाहर आएं
टेम्प := टेम्प + v[i]
काउंटर >= कट्स होने पर true लौटाएं
मुख्य मेथड से निम्नलिखित करें:
मैक्सा := -1
n := s का आकार
लो := 0, हाई := 0
i := 0 से शुरू करें, जब i < n, अपडेट करें (i को 1 से बढ़ाएं), करें:
लो := लो और s[i] का न्यूनतम
हाई := हाई + s[i]
(हाई को 1 से बढ़ाएं)
जब लो < हाई, करें:
मिड := लो + (हाई - लो + 1) / 2
यदि ok(s, k + 1, मिड) सत्य है, तो:
लो := मिड
अन्यथा:
हाई := मिड - 1
लो लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(vector v, int cuts, int maxVal) {
int counter = 0;
int temp = 0;
for (int i = 0; i <= v.size(); i++) {
if (temp >= maxVal) {
counter++;
temp = 0;
}
if (i == v.size()) {
break;
}
temp += v[i];
}
return counter >= cuts;
}
int maximizeSweetness(vector& s, int k) {
int maxa = -1;
int n = s.size();
int low = 0;
int high = 0;
for (int i = 0; i < n; i++) {
low = min(low, s[i]);
high += s[i];
}
high++;
while (low < high) {
int mid = low + (high - low + 1) / 2;
if (ok(s, k + 1, mid))
low = mid;
else
high = mid - 1;
}
return low;
}
};
int main() {
Solution ob;
vector v = {1,2,3,4,5,6,7,8,9};
cout << (ob.maximizeSweetness(v, 5));
}
इनपुट
{1,2,3,4,5,6,7,8,9}, 5
आउटपुट
6
