LeetCode 774. 最小化去加油站的最大距离（极小极大化 二分查找）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

假设我们在一条水平数轴上，列表 stations 来表示各个加油站的位置，加油站分别在 stations[0], stations[1], ..., stations[N-1] 的位置上，其中 N = stations.length。

现在我们希望增加 K 个新的加油站，使得相邻两个加油站的距离 D 尽可能的最小，请你返回 D 可能的最小值。

示例： 输入：stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9 输出：0.500000注： stations.length 是在范围 [10, 2000] 内的整数 stations[i] 是在范围 [0, 10^8] 内的整数 K 是在范围 [1, 10^6] 内的整数 在 10^-6 以内的正确值会被视为正确的答案

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimize-max-distance-to-gas-station
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

LeetCode 1231. 分享巧克力（极小极大化 二分查找）

• 模板题，预先求出每个站之间的距离，二分查找 d，检查最小间距d下，K个站够不够

class Solution { public:double minmaxGasDist(vector<int>& stations, int K) {int n = stations.size();vector<int> dis(n-1);for(int i = 1; i < n; ++i){dis[i-1] = stations[i]-stations[i-1];//加油站之间的距离}double l = 0, r = 1e8+1, d, ans;while(r-l >= 1e-7){d = (l+r)/2.0;if(isok(dis,d,K)){r = d;ans = d;}elsel = d;}return ans;}bool isok(vector<int>& dis, double d, int K){ //每个站之间的相邻距离为 d, 增加 K 个站够吗？int need = 0;for(int i = 0; i < dis.size(); ++i){need += ceil(dis[i]/d)-1;}return need <= K;} };

68 ms 13.3 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 774. 最小化去加油站的最大距离（极小极大化 二分查找）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。