मान लीजिए हमारे पास एक क्षैतिज संख्या रेखा है। उस संख्या रेखा पर, हमारे पास गैस स्टेशन positions stations[0], stations[1], ..., stations[N-1] पर हैं, जहां N = stations ऐरे का आकार है। अब, हम K और गैस स्टेशन जोड़ते हैं ताकि D, आसन्न गैस स्टेशनों के बीच अधिकतम दूरी, न्यूनतम हो। हमें D का न्यूनतम संभव मान ज्ञात करना है।
तो, यदि इनपुट stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9 है, तो आउटपुट 0.5 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
एक फ़ंक्शन ok() परिभाषित करें, जो x, ऐरे v लेगा,
ret := 0
i := 0 से शुरू करें, जब i < v का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
ret := ret + (v[i + 1] - v[i]) / x की सीलिंग
ret लौटाएं
मुख्य मेथड से निम्नलिखित करें:
लो := 0
n := s का आकार
हाई := s[n - 1] - s[0]
जब हाई - लो >= 1e-6, करें:
मिड := (लो + हाई) / 2.0
x := ok(मिड, s)
यदि x > K, तो:
लो := मिड
अन्यथा:
हाई := मिड
हाई लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int ok(double x, vector& v) {
int ret = 0;
for (int i = 0; i < v.size() - 1; i++) {
ret += ceil((v[i + 1] - v[i]) / x) - 1;
}
return ret;
}
double minmaxGasDist(vector& s, int K) {
double low = 0;
int n = s.size();
double high = s[n - 1] - s[0];
while (high - low >= 1e-6) {
double mid = (low + high) / 2.0;
int x = ok(mid, s);
if (x > K) {
low = mid;
} else {
high = mid;
}
}
return high;
}
};
int main() {
Solution ob;
vector v = {1,2,3,4,5,6,7,8,9,10};
cout << (ob.minmaxGasDist(v, 9));
}
इनपुट
{1,2,3,4,5,6,7,8,9,10}, 9
आउटपुट
0.5