首页 > 试题广场 >

现有一圆环形路，路上有n个加油站，第i个加油站储存有Ni升容

[问答题]
现有一圆环形路，路上有n个加油站，第i个加油站储存有Ni升容量的油，每两个加油站之间有一定的距离（km），一汽车初始无油，该车每公里消耗w升油，请问该车从哪个加油站出发可以绕该环形路行驶一圈。给出所有的算法及时间的复杂度。
查看答案及解析
添加回答
推荐
S.Xiao头像 S.Xiao
对这个问题，我提供三种解题思路：首先不妨设第i个加油站与之后加油站距离为g[i]/w，这样相当于每公里消耗1升油，这里的假设和量纲缩放并不影响实际结果，只是简化计算。

方法一：从左往右遍历，记住油量和最少的位置，从其下一个位置出发。 
int selectGasStation_1(const vector<int> &a, const vector<int> &g, const int n) {
    int res = 0, min = N[0] - g[0], sum = min;
    for (int i = 1; i < n; ++i)
    {
        sum += N[i] - g[i];
        if (sum < min) {
            min = sum;
            res = i;
        }
    }
    return sum >= 0 ? (res + 1) % n : -1;
}

方法二：开辟一个长度为N的数组v，记录N[i]-g[i]。从后往前遍历数组v。如果v[i]小于零，将其与v[i-1]合并，因为此时i不可能作为起点。如果v[i]不小于零，记入sum，并记录该位置pos（有可能作为起点）。最后，如果v[0]大于等于零，说明整个路段已经没有负的v[i]。返回0即可。如果v[0]+sum>=0，有满足条件的加油站，返回pos。否则，返回-1。 
int selectGasStation_2(const vector<int> &a, const vector<int> &g, const int n) {
    int v[n];
    for (int i = 0; i < n; ++i)
        v[i] = N[i] - g[i];
    int sum = 0, pos = -1;
    for (int i = n-1; i > 0; --i)
    {
        if (v[i] >= 0) {
            sum += v[i];
            pos = i;
        } else {
            v[i-1] += v[i];
        }
    }
    if (v[0] >= 0) return 0;
    else if (v[0] + sum >= 0) return pos;
    else return -1;
}

方法三：开辟一个长度为2*n-1的数组v，记录N[i]-g[i]（环转化为线性）。使用两个指针start和end。如果[start, end]区间和小于0，令start = end + 1并继续。直至找到长度为N的区间[start, end]，并且区间和大于等于0。找到返回start。 
int selectGasStation_3(const vector<int> &a, const vector<int> &g, const int n) {
    int v[2 * n];
    for (int i = 0; i < n; ++i)
    {
        v[i] = N[i] - g[i];
        v[i+n] = N[i] - g[i];
    }
    int sum = 0;
    for (int start = 0, end = 0; start <= n && end < 2 * n; end++)
    {
        if (sum + v[end] < 0) {
            start = end + 1;
            sum = 0;
        } else {
            if (end - start == n - 1) 
                return start;
            sum += v[end];
        }
    }
    return -1;
}

以上三种解法的时间复杂度均为O(n)，应该满足最苛刻的效率要求了。

编辑于 2015-01-28 17:24:52 回复(1)
崔佳彬头像 崔佳彬
总存在一个加油站，仅用它的油就足够跑到下一个加油站（否则所有加油站的油量加起来将不够全程）。把下一个加油站的所有油都提前搬到这个加油站来，并把油已被搬走的加油站无视掉。在剩下的加油站中继续寻找油量足以到达下个加油站的地方，不断合并加油站，直到只剩一个加油站为止。显然从这里出发就能顺利跑完全程。
另一种证明方法：先让汽车油箱里装好足够多的油，随便从哪个加油站出发试跑一圈。车每到一个加油站时，记录此时油箱里剩下的油量，然后把那个加油站的油全部装上。试跑完一圈后，检查刚才路上到哪个加油站时剩的油量最少，那么空着油箱从那里出发显然一定能跑完全程。
发表于 2014-12-14 00:14:18 回复(0)
碎痕头像 碎痕
[不知对不对]动态规划，首先压缩二维数组，s＝油-路程，从首位出发，上一个（环）若是正数或自己本身为负数，则递归计算上一位，若上一位是负数则遍历一遍计算能否开车绕行一圈 
    public static boolean[] status;

    public int startFrom(int s[],int i){
        if(status[i]==true)
            return -1;//找不到
        int n = s.length;
        if(s[i]<0||s[(i+n-1)%n]>0){
            return startFrom(s,(i+n-1)%n);
        }else{
            int j = i + 1;
            int sum = s[i];
            while((j+n+1)%n!=i){
                sum+=s[(j+n+1)%n];
                //失败
                if(sum<0)
                    return startFrom(s,(i+n-1)%n);
                j++;
            }
            status[i] = true;
            return i;
        }
    }
发表于 2016-09-04 09:45:37 回复(0)
血江南头像 血江南 
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int CanCircle(int station[],int gas[],int n,int w){
    int sumgas=0;
    int i=1;
    int time=n;      
    while(time>0){
        sumgas+=gas[i]-gas[i-1]-w*(station[i]-station[i-1]);
        if(sumgas<0)
        {
            sumgas=0;
            start=i;
            time=n;
        }else{
            time--;
        }
        i=(i+1)%n;        
    }
}
int main(){

    return 0;
}

发表于 2016-06-07 22:46:11 回复(0)
haha2015头像 haha2015
第n个考虑上一次加油的站点的可能性，可以以循环的方式获取或递归的方式获取，此算法的时间复杂度为O（n）
发表于 2015-05-06 10:26:58 回复(0)
Ph4nix头像 Ph4nix
1
发表于 2014-11-10 20:30:23 回复(0)
kangqiao182头像 kangqiao182

V   t  n-1  s

W * t = Ni

V*t = s/(n-1)

Ni = s/(n-1) * w

发表于 2014-11-04 13:30:35 回复(0)
kangqiao182头像 kangqiao182

V   t  n-1  s

W * t = Ni

V*t = s/(n-1)

Ni = s/(n-1) * w

发表于 2014-11-04 13:29:07 回复(0)
渔村战神懒小恩头像 渔村战神懒小恩

V   t  n-1  s

W * t = Ni

V*t = s/(n-1)

Ni = s/(n-1) * w

发表于 2014-10-25 00:26:08 回复(1)
提交观点

问题信息

模拟 京东 智力题
来自：京东2013研发笔试卷
上传者：牛客643913号
难度：
9条回答 14661浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号