Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में k सबलिस्ट्स के न्यूनतम सबसे बड़े योग को ढूंढने का प्रोग्राम

समस्या विवरण

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

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

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम बाइनरी सर्च का उपयोग करेंगे:

  1. एक फंक्शन ok() परिभाषित करें जो ऐरे v, k, x लेता है
  2. cnt := 0, sum := 0
  3. v के प्रत्येक तत्व i के लिए:
    • यदि sum + i > x, तो sum := i, cnt बढ़ाएं
    • अन्यथा sum := sum + i
  4. यदि cnt ≤ k तो true वापस करें, अन्यथा false
  5. मुख्य विधि से:
    • 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
  6. 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
  1. C++ में ट्री में सबसे बड़ा उपट्री योग ढूंढें C++ में ट्री में सबसे बड़ा उपट्री योग ढूंढें

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य ट्री में सबसे बड़ा उपट्री योग ढूंढना है। समस्या विवरण: बाइनरी ट्री में धनात्मक और ऋणात्मक दोनों मान होते हैं। और हमें वह उपट्री ढूंढनी है जिसमें नोड्स का अधिकतम योग हो। समस्या को समझने के लिए एक उदाहरण लेते हैं, आउटपुट: 13 व्याख्या: बाएं

  1. - C++ में अधिकतम योग वाले k नॉन-ओवरलैपिंग सबलिस्ट्स का योग ढूंढने का प्रोग्राम

    समस्या विवरण मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची और एक मान k है, हमें k नॉन-ओवरलैपिंग, नॉन-खाली सबलिस्ट्स ढूंढने हैं जैसे कि उनके योग का योग अधिकतम हो। हम मान सकते हैं कि k, nums के आकार से कम या बराबर है। उदाहरण के लिए, यदि इनपुट है nums = [11, -1, 2, 1, 6, -24, 11, -9, 6] k = 3, तो आ

  1. C++ में बाइनरी ट्री के उस स्तर को खोजें जिसका योग न्यूनतम है C++ में बाइनरी ट्री के उस स्तर को खोजें जिसका योग न्यूनतम है

    एक बाइनरी ट्री दिया गया है जहां रूट का स्तर 1 है। हमें वह सबसे छोटा स्तर X ढूंढना है जहां सभी नोड्स के मानों का योग न्यूनतम हो। उदाहरण ट्री में रूट 5 है, बाएं 4, दाएं -10, आदि। स्तर 2 का योग 4 + (-10) = -6 है, जो न्यूनतम है, इसलिए आउटपुट 2 है। समाधान दृष्टिकोण हम लेवल ऑर्डर ट्रैवर्सल (BFS) का उपयोग