สมมติว่าเรามีเส้นจำนวนแนวนอนหนึ่งเส้น บนเส้นจำนวนนั้น เรามีปั๊มน้ำมันที่ตำแหน่ง station[0], สถานี[1], ..., สถานี[N-1] โดยที่ N =ขนาดของอาร์เรย์สถานี ตอนนี้ เราเพิ่มสถานีบริการน้ำมัน K มากขึ้น เพื่อลดระยะห่างสูงสุดระหว่างสถานีบริการน้ำมันที่อยู่ติดกัน D เราต้องหาค่า D ที่น้อยที่สุดที่เป็นไปได้
ดังนั้น หากอินพุตเหมือนกับสถานี =[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K =9 เอาต์พุตจะเป็น 0.5
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน ok() ซึ่งจะใช้ x, array v
-
ยกเลิก :=0
-
สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
ret :=ret + เพดานของ (v[i + 1] - v[i]) / x
-
-
รีเทิร์น
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
ต่ำ :=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 <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));
} อินพุต
{1,2,3,4,5,6,7,8,9,10}, 9 ผลลัพธ์
0.5
