पहला सर्कुलर टूर खोजें जो सभी पेट्रोल पंपों को विज़िट करे C++ प्रोग्राम में

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

• हर पेट्रोल पंप पर पेट्रोल की मात्रा
• एक पेट्रोल पंप से दूसरे तक की दूरी।

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

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

उदाहरण

#include <iostream>
using namespace std;

class pump {
public:
    int petrol;
    int distance;
};

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

int main() {
    pump PumpArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}};
    int n = sizeof(PumpArray) / sizeof(PumpArray[0]);
    int start = findStartIndex(PumpArray, n);
    if (start == -1)
        cout << "No solution";
    else
        cout << "Index of first petrol pump: " << start;
}

आउटपुट

Index of first petrol pump: 1