मान लीजिए सीधी रेखा में 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
