資料結構
網路
關係資料庫管理系統 (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+
廣告