C++-汽车环岛一周

C++-汽车环岛一周

归属感 发布于 2016-12-12 字数 510 浏览 1093 回复 2

请输入图片描述

如:上图,有一个环形的岛,岛上面有若干个加油站,每两个相邻加油站的之间的距离已知,每个加油站拥有的油量也知道。现在有一辆汽车,该汽车的油箱无限大,初始时油箱为空。
问:该汽车从某个加油站出发,是否能环岛一周回到原地?如果能,是从哪个加油站开始?

设:每两个相邻加油站的距离相等,为L;岛上有N个加油站,每个加油站拥有的油量用数组V[N]表示;汽车每公里耗油的速率为d。
要求:请用O(n)的方法实现。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

归属感 2017-01-09 2 楼

算法思路

我们先对V[]作下简化处理 对每个V[i]-=L*d

这样就得到每个V[i]相对基本需求油量的大小关系。(这个值表示该加油站的油量减去到下一个加油站的耗油量L*d。如果值为正说明该加油站还有剩余的油供给汽车在后面的路程中使用;如果值为负表示该加油站需要前面加油站提供额外的油来到达下一个加油站。)
处理后如果我们找到一条路径从起点到终点一路累加V[i]的和sum,
如果sum一直不小于0 说明这条路径就是一条符合题意的路径。
算法始终要依次枚举一个点作为起点。如果直接枚举显然不能做到O(n)时间。要采取动态规划思想。下面是算法:

初始化sum=0,len=0(len表示我们已经累加的加油站个数)
我们从 i=0 开始依次累加sum+=V[i%n] ,每累加一次后:
(这里要注意应把i看作我们枚举的尾部,仔细想想。i要满足条件i<2*n(因为我们枚举时V[n-1]->V[0]->V[1]->....->V[n-2]是最后一条可能路径)取模是为了绕个圈)

如果sum<0说明这条路径不可行:
这里要注意一个算法的核心:这里在这条我们尝试失败的路径也就是 V[i-len+1]到V[i] 这段不可能存在一个合法的起点。设想如果这段存在一个合法起点j,那么V[j]到V[i]累加肯定>=0。然而V[i-len+1]到V[j-1]也肯定是>=0,这样此时的sum也就>=0,矛盾!所以我们就不必枚举i-len+1到V[i]之间的作为起点了,这就是为什么算法能够在O(n)完成
接着上面条件(sum<0)置len=0;sum=0;(即以下一个作为起点尝试)
如果sum>=0:路径到这里没有问题
len+=1;
如果len==n:说明我们找到了一条合法路径,起点为i-len+1 算法结束;

i+=1;往后枚举。
循环结束:
此时若没有找到合法路径,则不存在合法路径,算法结束。
算法时间复杂度O(n)。

算法代码

int circle(int *d,int n,int Ld){ //Ld=L*d
for(int i=0;i<n;++i) //O(n)
d[i]-=Ld;
int len=0,sum=0;
for(int i=0;i<(n<<1);++i){
sum+=d[i%n];
if(sum<0){
sum=0;
len=0;
}
else
if(++len==n)//answer
return i-n+1;
}
return -1; //no answer
}

晚风撩人 2017-01-06 1 楼

假设找到的 V[0] 的点就是可以作为出发点的点(0 点不是固定某个点,是假设的)。那么就必须满足一下条件

V[0] >= L * d;
V[1] >= V[0] - 2 * L * d;
V[2] >= V[1] + V[0] - 3 * L * d;
V[n-1] >= V[n-2] + V[n-3] + ... V[0] - n * L * d;

所以可以得出通式:

V[i] >= V[i-1] + V[i-2] + ... V[0] - (i+1) * L * d;

根据这个通式,遍历 i 从 0 ~ n-1 找到出发点。