สมมติว่าเรามีเส้นจำนวนแนวนอนหนึ่งเส้น บนเส้นจำนวนนั้น เรามีสถานีน้ำมันอยู่ที่ตำแหน่ง 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
for i := 0 ถึงขนาดของ v - 2: ret += ceil((v[i+1] - v[i]) / x) - 1
คืนค่า ret
จาก main method:
low := 0
n := ขนาดของ s
high := s[n-1] - s[0]
while high - low ≥ 1e-6:
mid := (low + high) / 2.0
x := ok(mid, s)
ถ้า x > K: low := mid มิฉะนั้น high := mid
คืนค่า high
ตัวอย่างโค้ด
#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));
return 0;
}
อินพุต
{1,2,3,4,5,6,7,8,9,10}, 9
เอาต์พุต
0.5
