| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛

[抄道题] 加油站
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

int gas[] = { 5, 2, 6, 3 };
int cst[] = { 4, 4, 4, 4 };    question: 可以逆行么???? [fly]存在即是合理[/fly]    question: 可以逆行么????          程序代码：
```#include<stdio.h>
int CompleteCircuit( int n, const int gas[], const int cost[] )
{
int i,j,k,l;
for(i=0;i<n;i++)
{
for(j=i,l=0;j<i+n;j++)
{
k=j%n;
l+=gas[k]-cost[k];
if(l<0)break;
}
if(l>=0)return i;
}
return -1;
}
void main()
{
int o[]={5,2,6,3},e[]={4,4,4,4};
printf("%d\n",CompleteCircuit(4,o,e));
}
```      程序代码：
```#include <stdio.h>

int CompleteCircuit(int n, const int gas[], const int cost[])
{
int pos = -1, sum = 0, tmp = 0;

for (int i = n - 1;i >= 0;i--)
{
sum += gas[i] - cost[i];
tmp += gas[i] - cost[i];
if (tmp >= 0)  pos = i, tmp = 0;
}
return sum >= 0 ? pos : -1;
}

int main()
{
int N = 4;
int gas[] = {5, 2, 6, 3}, cost[] = {4, 4, 4, 4};

printf("%d\n", CompleteCircuit(N, gas, cost));

return 0;
}
``` [fly]存在即是合理[/fly]    • 6
• 1/1页
• • 1
• 