मान लीजिए हमारे पास एक चॉकलेट बार है जिसमें कुछ टुकड़े हैं। प्रत्येक खंड में इसकी अपनी मिठास होती है जिसे मिठास नामक सूची द्वारा दिया जाता है। अगर हम K दोस्तों के बीच चॉकलेट बांटना चाहते हैं तो हम K कट्स का उपयोग करके चॉकलेट बार को K+1 पीस में काटना शुरू करते हैं, अब प्रत्येक पीस में कुछ लगातार टुकड़े होते हैं। अगर हम कम से कम कुल मिठास के साथ टुकड़ा निकालते हैं और बाकी के टुकड़े अपने दोस्तों को देते हैं। हमें चॉकलेट बार को बेहतर तरीके से काटकर उस टुकड़े की अधिकतम कुल मिठास का पता लगाना होगा जो हम प्राप्त कर सकते हैं।
इसलिए, यदि इनपुट मिठास की तरह है =[1,2,3,4,5,6,7,8,9], K =5, तो आउटपुट 6 होगा क्योंकि आप चॉकलेट को [1,2 में विभाजित कर सकते हैं ,3], [4,5], [6], [7], [8], [9] ये टुकड़े।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन को परिभाषित करें ठीक (), यह एक सरणी v, कट्स, मैक्सवैल,
लेगा -
काउंटर:=0, अस्थायी:=0
-
इनिशियलाइज़ i :=0 के लिए, जब i <=v का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -
-
अगर अस्थायी>=मैक्सवैल, तो
-
(काउंटर 1 से बढ़ाएं)
-
अस्थायी:=0
-
-
यदि i, v के आकार के समान है, तो -
-
लूप से बाहर आएं
-
-
अस्थायी:=अस्थायी + वी[i]
-
-
काउंटर>=कट्स
. होने पर सही लौटें -
मुख्य विधि से निम्न कार्य करें:
-
मैक्सा:=-1
-
n :=s का आकार
-
निम्न :=0, उच्च :=0
-
इनिशियलाइज़ i:=0 के लिए, जब i
-
निम्न :=न्यूनतम निम्न और s[i]
-
उच्च:=उच्च + एस[i]
-
-
(उच्च 1 से बढ़ाएँ)
-
जबकि कम <उच्च, करें -
-
मध्य :=निम्न + (उच्च - निम्न + 1) / 2
-
यदि ओके(एस, के + 1, मिड) सत्य है, तो -
-
कम :=मध्य
-
-
अन्यथा
-
उच्च :=मध्य - 1
-
-
-
कम वापसी
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(vector <int> 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<int>& 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;
}
};
main(){
Solution ob;
vector<int> 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