本文共 1120 字,大约阅读时间需要 3 分钟。
On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., stations[N-1], where N = stations.length.
Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.
Return the smallest possible value of D.
Example:
Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output: 0.500000
Note:
1、 stations.length will be an integer in range [10, 2000].
2、 stations[i] will be an integer in range [0, 10^8].
3、 K will be an integer in range [1, 10^6].
4、 Answers within 10^-6 of the true value will be accepted as correct.
贪心肯定不对,参考discuss,假设一个结果,然后对结果进行二分逼近。
public double minmaxGasDist(int[] stations, int K) {
int LEN = stations.length;
double left = 0, right = stations[LEN - 1] - stations[0], mid = 0;
while (right >= left + 0.000001) {
mid = right - (right - left) / 2;
int cnt = 0;
for (int i = 0; i < LEN - 1; i++) {
cnt += Math.ceil((stations[i + 1] - stations[i]) / mid) - 1; //重点理解代码,d_i / (cnt_i + 1) <= mid
}
if (cnt > K) {
left = mid;
} else {
right = mid;
}
}
return mid;
}
https://www.cnblogs.com/wxisme/category/672272.html
转载地址:https://blog.csdn.net/weixin_32473663/article/details/114518845 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!