하나의 수평 숫자 라인이 있다고 가정합니다. 해당 번호 라인에는 스테이션[0], 스테이션[1], ..., 스테이션[N-1] 위치에 주유소가 있습니다. 여기서 N =스테이션 배열의 크기입니다. 이제 인접한 주유소 간의 최대 거리 D가 최소화되도록 K 주유소를 추가합니다. D의 가능한 가장 작은 값을 찾아야 합니다.
따라서 입력이 스테이션 =[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K =9와 같으면 출력은 0.5
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ok() 함수를 정의하면 x, 배열 v,
가 필요합니다. -
ret :=0
-
initialize i :=0의 경우 i
-
ret :=ret + (v[i + 1] - v[i]) / x
의 상한
-
-
리턴 렛
-
주요 방법에서 다음을 수행하십시오 -
-
낮음 :=0
-
n :=s
의 크기 -
높음 :=s[n - 1] - s[0]
-
높음 - 낮음>=1e-6인 동안 −
-
중간 :=(낮음 + 높음) / 2.0
-
x :=ok(중간, 초)
-
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