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

न्यूनतम ईंधन भरने के स्टॉप C++ में

मान लीजिए एक कार है, जो एक प्रारंभिक स्थिति से एक गंतव्य तक यात्रा करती है जो प्रारंभिक स्थिति से t मील पूर्व में है।

रास्ते में कई गैस स्टेशन हैं। प्रत्येक station[i] एक गैस स्टेशन को दर्शाता है जो station[i][0] मील पूर्व में है, और जिसमें station[i][1] लीटर गैस है।

यदि कार अनंत आकार के गैस टैंक के साथ शुरू होती है, जिसमें शुरू में startFuel लीटर ईंधन होता है। यह प्रति मील 1 लीटर गैस का उपयोग करती है।

जब कार एक गैस स्टेशन पर पहुंचती है, तो वह रुककर ईंधन भर सकती है, स्टेशन से कार में सारी गैस ट्रांसफर हो जाती है। हमें वह न्यूनतम ईंधन भरने के स्टॉप की संख्या ढूंढनी है जो कार को अपने गंतव्य तक पहुंचने के लिए करने होंगे? यदि गंतव्य तक पहुंचना असंभव है, तो -1 वापस करें।

उदाहरण के लिए, यदि लक्ष्य = 100, startFuel = 20, stations = [[10,40],[20,30],[30,20],[60,40]], तो आउटपुट 3 होगा।

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

हम एक लालची दृष्टिकोण का उपयोग करते हैं जिसमें मैक्स-हीप (प्रायोरिटी क्यू) होता है:

  • स्टेशन को स्थिति के अनुसार सॉर्ट करें

  • पहुंच योग्य स्टेशनों के ईंधन को मैक्स-हीप में डालें

  • जब वर्तमान ईंधन अगले स्टेशन/लक्ष्य तक पहुंचने के लिए अपर्याप्त हो, तो सबसे बड़े ईंधन वाले स्टेशन पर रुकें

  • स्टॉप गिनें जब तक लक्ष्य पहुंच योग्य न हो या हीप खाली न हो

उदाहरण

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

class Solution { 
public: 
    int minRefuelStops(int target, int fuel, vector<vector<int>> &st) { 
        int curr = 0; 
        sort(st.begin(), st.end()); 
        priority_queue<int> pq; 
        int i = 0; 
        int cnt = 0; 
        curr += fuel; 
        
        while (curr < target) { 
            cnt++; 
            while (i < st.size() && st[i][0] <= curr) { 
                pq.push(st[i][1]); 
                i++; 
            } 
            if (pq.empty()) break; 
            curr += pq.top(); 
            pq.pop(); 
        } 
        return curr >= target ? cnt : -1; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<int>> v = {{10,40},{20,30},{30,20},{60,40}}; 
    cout << (ob.minRefuelStops(100, 10, v)); 
    return 0;
}

इनपुट

100, 10, {{10,40},{20,30},{30,20},{60,40}}

आउटपुट

3
  1. - C++ में मितव्ययी संख्या (Frugal Number)

    इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया गया है। हमारा कार्य यह जांचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं। मितव्ययी संख्या (FRUGAL NUMBER) − एक संख्या जिसके अंकों की संख्या उस संख्या के अभाज्य गुणनखंडन में अंकों की संख्या से सख्ती से अधिक है। उदाहरण &

  1. C++ में पेंटाटोप संख्या C++ में पेंटाटोप संख्या

    एक पेंटाटोप संख्या को पास्कल के त्रिभुज में पांचवीं संख्या के रूप में वर्णित किया गया है। अब, चूंकि यह पांचवीं संख्या है, इसका मतलब है कि पास्कल के त्रिभुज में कम से कम पांच संख्याएं होनी चाहिए, इसलिए इस श्रृंखला की पहली संख्या 1 4 6 4 1 से शुरू होती है जो पास्कल के त्रिभुज की चौथी पंक्ति है। तो, इस

  1. - C++ में न्यूनतम पृष्ठों का आवंटन

    न्यूनतम पृष्ठों का आवंटन एक प्रोग्रामिंग समस्या है। आइए इस समस्या पर विस्तार से चर्चा करते हैं और देखते हैं कि इसका समाधान क्या हो सकता है। कथन आपको n विभिन्न पुस्तकों के पृष्ठों की संख्या दी गई है। साथ ही, m छात्र हैं जिन्हें पुस्तकें आवंटित की जानी हैं। पुस्तकें पृष्ठों की संख्या के आरोही क्रम में