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

C++ में ब्लॉक्स बनाने का न्यूनतम समय

मान लीजिए हमारे पास ब्लॉक्स की एक सूची है, यदि blocks[i] = t है, तो इसका मतलब है कि i-वां ब्लॉक बनाने के लिए t यूनिट समय की आवश्यकता है। एक ब्लॉक को ठीक एक वर्कर द्वारा ही बनाया जा सकता है। सिंगल वर्कर या तो दो वर्कर्स में विभाजित हो सकता है या एक ब्लॉक बना सकता है फिर घर जा सकता है। इन दोनों निर्णयों में कुछ समय लगता है। एक वर्कर को दो वर्कर्स में विभाजित करने की समय लागत split नामक संख्या के रूप में दी जाती है।

तो, यदि इनपुट blocks = [1,2], और split = 5 है, तो आउटपुट 7 होगा क्योंकि हम वर्कर को 5 समय यूनिट में 2 वर्कर्स में विभाजित कर सकते हैं फिर उनमें से प्रत्येक को एक ब्लॉक असाइन कर सकते हैं इसलिए लागत 5 + max(1, 2) = 7 है।

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

  • एक प्रायोरिटी क्यू pq परिभाषित करें

  • i := 0 से शुरू करें, जब i < blocks का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:

    • blocks[i] को pq में डालें

  • जब pq का आकार > 1, करें:

    • pq से एलिमेंट डिलीट करें

    • x := pq का टॉप एलिमेंट

    • pq से एलिमेंट डिलीट करें

    • split + x को pq में डालें

  • pq का टॉप एलिमेंट लौटाएं

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minBuildTime(vector& blocks, int split) {
        priority_queue, greater> pq;
        for (int i = 0; i < blocks.size(); i++)
            pq.push(blocks[i]);
        while (pq.size() > 1) {
            pq.pop();
            int x = pq.top();
            pq.pop();
            pq.push(split + x);
        }
        return pq.top();
    }
};

int main() {
    Solution ob;
    vector v = {1,2};
    cout << (ob.minBuildTime(v, 5));
}

इनपुट

{1,2}, 5

आउटपुट

7
  1. C/C++ में बर्कले का एल्गोरिथ्म C/C++ में बर्कले का एल्गोरिथ्म

    बर्कले का एल्गोरिथ्म वितरित प्रणालियों में क्लॉक सिंक्रोनाइज़ेशन के लिए उपयोग किया जाने वाला एक एल्गोरिथ्म है। यह एल्गोरिथ्म उन मामलों में उपयोग किया जाता है जब वितरित नेटवर्क के कुछ या सभी सिस्टम में निम्नलिखित समस्याएं होती हैं: A. मशीन के पास सटीक समय स्रोत नहीं है। B. नेटवर्क या मशीन के पास UTC

  1. C++ में बाइनरी ट्री की न्यूनतम गहराई C++ में बाइनरी ट्री की न्यूनतम गहराई

    समस्या विवरण मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उस ट्री की न्यूनतम गहराई ज्ञात करनी है। जैसा कि हम जानते हैं, न्यूनतम गहराई रूट नोड से निकटतम लीफ नोड तक के सबसे छोटे पथ पर नोड्स की संख्या है। उदाहरण यदि इनपुट ट्री है: तो आउटपुट होगा 2 हल करने का दृष्टिकोण इस समस्या को हल करने के लिए निम

  1. C++ में न्यूनतम नाइट मूव्स C++ में न्यूनतम नाइट मूव्स

    मान लीजिए हमारे पास एक अनंत शतरंज बोर्ड है जिसके कोऑर्डिनेट्स -इनफिनिटी से +इनफिनिटी तक हैं, और हमारे पास [0, 0] स्क्वायर पर एक नाइट है। नाइट के 8 संभावित मूव्स होते हैं, जैसा कि नीचे दिखाया गया है। प्रत्येक मूव कार्डिनल डायरेक्शन में दो स्क्वायर, फिर ऑर्थोगोनल डायरेक्शन में एक स्क्वायर होता है। ह