C++ में k सबलिस्ट्स की न्यूनतम सबसे बड़ी राशि खोजने का कार्यक्रम

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k है। हम सूची को k गैर-रिक्त उप-सूचियों में विभाजित कर सकते हैं। हमें k उप-सूचियों का न्यूनतम सबसे बड़ा योग ज्ञात करना है।

इसलिए, यदि इनपुट संख्या =[2, 4, 3, 5, 12] k =2 की तरह है, तो आउटपुट 14 होगा, क्योंकि हम सूची को विभाजित कर सकते हैं जैसे:[2, 4, 3, 5] और [ 12].

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें ठीक (), यह सरणी v, k, x,

  लेगा

• सीएनटी:=0, योग:=0

• v −

  . में प्रत्येक तत्व i के लिए

  • यदि योग + i> x, तो -

    • योग :=मैं

    • (cnt 1 से बढ़ाएँ)

  • अन्यथा

    • योग :=योग + मैं

• जब cnt <=k, अन्यथा असत्य

• मुख्य विधि से निम्न कार्य करें -

• निम्न:=0, सेवानिवृत्त:=0, उच्च:=0

• प्रत्येक तत्व के लिए मैं अंकों में

  • उच्च:=उच्च + मैं

  • रिट:=रिट + आई

  • निम्न :=अधिकतम निम्न और i

• जबकि कम <=उच्च, करें −

  • मध्य:=निम्न + (उच्च-निम्न)/2

  • यदि ठीक है (अंक, के -1, मध्य) सत्य है, तो -

    • रिट:=मध्य

    • उच्च :=मध्य - 1

  • अन्यथा

    • कम :=मध्य + 1

• वापसी रिट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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;
   int ret = 0;
   int 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