Giả sử chúng ta có một đường thẳng số ngang. Trên đường thẳng đó, chúng ta có trạm xăng tại vị trí stations[0], stations[1], ..., stations[N-1], với N = kích thước mảng stations. Bây giờ, chúng ta thêm K trạm xăng nữa sao cho D, khoảng cách lớn nhất giữa các trạm xăng liền kề, được tối thiểu hóa. Chúng ta phải tìm giá trị nhỏ nhất có thể của D.
Vì vậy, nếu đầu vào là stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9, đầu ra sẽ là 0.5
Để giải quyết, chúng ta sẽ làm theo các bước:
Định nghĩa hàm ok(), nhận x, mảng v,
ret := 0
Khởi tạo i := 0, khi i < kích thước v, cập nhật (tăng i lên 1), làm:
ret := ret + ceiling của (v[i + 1] - v[i]) / x
Trả về ret
Từ phương thức main làm sau:
low := 0
n := kích thước s
high := s[n - 1] - s[0]
Khi high - low >= 1e-6, làm:
mid := (low + high) / 2.0
x := ok(mid, s)
nếu x > K, thì:
low := mid
Ngược lại
high := mid
Trả về high
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int ok(double x, vector <int>& 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<int>& 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; } }; main(){ Solution ob; vector<int> v = {1,2,3,4,5,6,7,8,9,10}; cout << (ob.minmaxGasDist(v, 9)); }Đầu vào
{1,2,3,4,5,6,7,8,9,10}, 9Đầu ra
0.5