मान लीजिए एक सीधी रेखा में N स्टेशन हैं। उनमें से प्रत्येक की विकिरण शक्ति समान गैर-नकारात्मक है। प्रत्येक स्टेशन अपने पड़ोसी स्टेशनों की विकिरण शक्ति को निम्न तरीके से बढ़ा सकता है।
मान लीजिए विकिरण शक्ति R वाला स्टेशन i, (i-1)वें स्टेशन की विकिरण शक्ति को R-1 से, (i-2)वें स्टेशन की विकिरण शक्ति को R-2 से बढ़ाएगा, और (i+1)वें स्टेशन की विकिरण शक्ति को R-1 से, (i+2)वें स्टेशन की विकिरण शक्ति को R-2 से बढ़ाएगा। इत्यादि। इसलिए उदाहरण के लिए, यदि सरणी Arr = [1, 2, 3] की तरह है, तो आउटपुट 3, 4, 4 होगा। नया विकिरण [1 + (2 - 1) + (3 - 2), 2 + (1 - 1) + (3 - 1), 3 + (2 - 1)] = [3, 4, 4] होगा।
विचार सरल है। प्रत्येक स्टेशन i के लिए ऊपर बताए अनुसार पड़ोसी स्टेशनों की विकिरण को बढ़ाएं, जब तक प्रभावी विकिरण ऋणात्मक न हो जाए।
उदाहरण
#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
