C++ में गैस स्टेशन (Gas Station)

मान लीजिए एक वृत्त है, और उस पर n गैस स्टेशन हैं। हमारे पास दो डेटा सेट हैं:

• हर गैस स्टेशन पर गैस की मात्रा
• एक गैस स्टेशन से दूसरे तक की दूरी।

पहला बिंदु ढूंढें, जहां से एक कार वृत्त पूरा कर सके। मान लें 1 इकाई गैस से कार 1 इकाई दूरी तय कर सकती है। मान लीजिए चार गैस स्टेशन हैं, और गैस की मात्रा, और अगले गैस स्टेशन तक की दूरी [(4, 6), (6, 5), (7, 3), (4, 5)] जैसी है, तो पहला बिंदु जहां से कार वृत्ताकार यात्रा कर सकती है, दूसरा गैस स्टेशन है। आउटपुट होना चाहिए start = 1 (दूसरे गैस स्टेशन का इंडेक्स)।

इस समस्या को कतार (queue) का उपयोग करके कुशलता से हल किया जा सकता है। कतार का उपयोग वर्तमान यात्रा को संग्रहीत करने के लिए किया जाएगा। हम पहले गैस स्टेशन को कतार में डालेंगे, हम गैस स्टेशन डालते रहेंगे, जब तक हम या तो यात्रा पूरी नहीं कर लेते, या गैस की वर्तमान मात्रा ऋणात्मक नहीं हो जाती। यदि मात्रा ऋणात्मक हो जाती है, तो हम तब तक गैस स्टेशन हटाते रहेंगे जब तक यह खाली न हो जाए।

उदाहरण

#include <iostream>
using namespace std;

class gas {
public:
    int gas;
    int distance;
};

int findStartIndex(gas stationQueue[], int n) {
    int start_point = 0;
    int end_point = 1;
    int curr_gas = stationQueue[start_point].gas - stationQueue[start_point].distance;
    while (end_point != start_point || curr_gas < 0) {
        while (curr_gas < 0 && start_point != end_point) {
            curr_gas -= stationQueue[start_point].gas - stationQueue[start_point].distance;
            start_point = (start_point + 1) % n;
            if (start_point == 0)
                return -1;
        }
        curr_gas += stationQueue[end_point].gas - stationQueue[end_point].distance;
        end_point = (end_point + 1) % n;
    }
    return start_point;
}

int main() {
    gas gasArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
    int n = sizeof(gasArray)/sizeof(gasArray[0]);
    int start = findStartIndex(gasArray, n);
    if(start == -1)
        cout << "कोई समाधान नहीं";
    else
        cout << "पहले गैस स्टेशन का इंडेक्स: " << start;
}

इनपुट

[[4, 6], [6, 5], [7, 3], [4, 5]]

आउटपुट

पहले गैस स्टेशन का इंडेक्स: 1