数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中最小化到加油站的最大距离
假设我们有一条水平数轴。在这条数轴上，我们在位置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，当 i < v 的大小，更新（i增加1），执行：
ret := ret + (v[i + 1] - v[i]) / x 的上取整
返回 ret
从主方法执行以下操作：
low := 0
n := s 的大小
high := s[n - 1] - s[0]
while high - low >= 1e-6，执行：
mid := (low + high) / 2.0
x := ok(mid, s)
if x > K，则：
low := mid
否则
high := mid
返回 high
让我们看看下面的实现来更好地理解：
示例
#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
更新于：2020年7月11日
浏览量 1K+
广告