算法：加油站良好的出发点

77 阅读 0 评论 51 点赞

我是靠谱客的博主大意戒指，最近开发中收集的这篇文章主要介绍算法：加油站良好的出发点，觉得挺不错的，现在分享给大家，希望可以做个参考。

N个加油站逆时针组成一个环，每个加油站最多加oil[i]的油量，该加油站距下个加油站距离dis[i]，1个油可以走1个距离，初始车里没有油，则从哪些加油站出发可以逆时针一圈后回到出发点。

类似dp的思维题，时间O(N)

该方法实现O(N)的核心思想在于，先找到一个良好出发点，再顺时针找可以到达该良好出发点的出发点，即新良好出发点，依次顺时针找，若顺时针一圈后仍然没有良好出发点，则所有点都不会是。

过程如下：

首先，数组实现环结构，每个元素代表加油站，Arr[i] 取值为 oil[i] - dis[i] ，其中，oil[i] 为当前加油站提供的油，dis[i] 为从加油站 i 到加油站 i+1 的距离，其中 i+1 可以返回到数组0位置。Arr[i] 新值可以称为净值。

由于车走的方向是逆时针，所以思维处理该题，逆时针扩充联通块，顺时针考查起始位置。

首先，所有净值小于0的加油站一定不满足要求。

所以，先从考查任意净值大于等于0的起始点，然后逆时针扩充联通块。

若能逆时针扩充一圈后回来，则该点是良好出发点，否则不是，同时标记联通块计算的结尾点。

然后从考查点顺时针考查下个不为0的点，是否可以扩充到刚才的考查点，不可以则一定不是良好出发点，若可以，再考查是否可以从刚才结尾点继续扩充一圈，依次类推。。

以上就是大意戒指为你收集整理的算法：加油站良好的出发点的全部内容，希望文章能够帮你解决算法：加油站良好的出发点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。