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