首页 > 试题广场 >

给出你认为最有效的算法，并评估时间复杂度

[问答题]

现有一圆形环路，路上有n个加油站，第i个加油站存储有Ni升容量的油，每两个加油站之间有一定的距离(km)，一汽车初始无油，该车每公里消耗w升油，请问该车从哪个加油站触发可以绕该环形炉形式一圈。返回可行的起始加油站编号（1~n）。如果有多解，则随机给出任意一个满足条件的起始加油站编号；无解则返回0。给出你认为最有效的算法，并评估时间复杂度。
gas[i]是i油站油量;distance[i]是第i站到下一站的距离;n是加油站个数;w是每公里消耗的油量
 
int startingPoint(int
gas[], int distance[], int n, int w){//your code}
 
注意：如果试用的算法异常另类或复杂，建议在解答里加上一些解题描述。

推荐

马克123

此题可以用数学归纳法的方法来证明

设置一个增量 diff= gas[i]-distance[i]*w；
那么我们的增量和如果大于0，是否就一定能到找一条可通路呢
下面是数学归纳法：
有些草率但是言简意赅

//接下来的问题就是如何找到从哪里出发，这里我直接给出代码
	public int startingPoint(int gas[], int distance[], int n, int w){
		int total= 0;
		int tank= 0;
		int begin= 0;
		for(int i= 0; i< n; i++){
			int diff= gas[i]- distance[i]* w;
			total+= diff;
			if( diff+tank >= 0 ){
				tank+= diff;
			}else{
				begin= i+1;
				tank= 0;
			}
		}
		return total>0&&begin<n?begin:0;
		
	}

编辑于 2017-05-23 17:24:46 回复(0)