| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 930 人关注过本帖
标题:[抄道题] 加油站
只看楼主 加入收藏
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:309
帖 子:6474
专家分:37499
注 册:2011-1-18
结帖率:90.91%
  已结贴   问题点数:100  回复次数:5   
[抄道题] 加油站
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.

环形公路上有N座加油站,第i座加油站储有gas[i]升油。
你有一辆油箱无限大的小汽车,它从第i座加油站行驶到第i+1座加油站需要耗费cost[i]升油。
假设一开始油箱内无油,请问你从第几座加油站出发可以绕环形公路一圈?
如果能,返回出发点的加油站序号(有多个的话取值最小的序号);如果不能,返回 -1。
提示,N大于等于1,也不需要考虑int的溢出问题。
函数原型 int CompleteCircuit( size_t n, const int gas[], const int cost[] );

如图

int gas[] = { 5, 2, 6, 3 };
int cst[] = { 4, 4, 4, 4 };
从第0座加油站出发的话,将会在到达第2座加油站前燃油耗尽;
从第1座加油站出发的话,将会在到达第2座加油站前燃油耗尽;
从第2座加油站出发的话,能绕一圈顺利回到出发点;
从第3座加油站出发的话,将会在到达第0座加油站前燃油耗尽;
所以应该返回 2。
附件: 您没有浏览附件的权限,请 登录注册
搜索更多相关主题的帖子: otherwise solution starting 加油站 journey 
2015-08-29 13:34
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
  得分:0 
question: 可以逆行么????


[fly]存在即是合理[/fly]
2015-08-29 14:29
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:309
帖 子:6474
专家分:37499
注 册:2011-1-18
  得分:0 
以下是引用azzbcc在2015-8-29 14:29:14的发言:

question: 可以逆行么????
不可以^_^
2015-08-29 14:36
w2009w
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:2
帖 子:190
专家分:542
注 册:2015-4-20
  得分:0 
2015-08-29 14:45
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:175
帖 子:1784
专家分:10015
注 册:2014-12-6
  得分:50 
正空闲,娱乐下。烦请rjsp版主做下极端测试!
程序代码:
#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));
}


能编个毛线衣吗?
2015-08-29 18:30
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
  得分:50 
程序代码:
#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]
2015-08-29 19:46







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030136 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved