Giả sử chúng ta có một đường số nằm ngang. Trên trục số đó, ta có các trạm xăng tại các vị trí trạm [0], trạm [1], ..., trạm [N-1], trong đó N =kích thước của mảng trạm. Bây giờ, chúng ta thêm K thêm trạm xăng sao cho D, khoảng cách lớn nhất giữa các trạm xăng liền kề, được giảm thiểu. Chúng ta phải tìm giá trị nhỏ nhất có thể có của D.
Vì vậy, nếu đầu vào giống như các trạm =[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K =9, thì đầu ra sẽ là 0,5
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm ok (), điều này sẽ lấy x, mảng v,
-
ret:=0
-
để khởi tạo i:=0, khi i
-
ret:=ret + trần của (v [i + 1] - v [i]) / x
-
-
trả lại ret
-
Từ phương thức chính, hãy làm như sau -
-
thấp:=0
-
n:=kích thước của s
-
cao:=s [n - 1] - s [0]
-
trong khi high - low> =1e-6, do -
-
giữa:=(thấp + cao) / 2.0
-
x:=ok (giữa, s)
-
nếu x> K, thì -
-
thấp:=trung bình
-
-
Nếu không
-
cao:=giữa
-
-
-
trả về cao
Hãy cùng chúng tôi xem cách 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