首页 > 试题广场 >

加油站良好出发点问题

[编程题]加油站良好出发点问题

热度指数：1542 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

N个加油站组成一个环形，给定两个长度都是N的非负数组oil和dis(N>1)，oil[i]代表第i个加油站存的油可以跑多少千米，dis[i]代表第i个加油站到环中下一个加油站相隔多少千米。假设你有一辆油箱足够大的车，初始时车里没有油。如果车从第i个加油站出发，最终可以回到这个加油站，那么第i个加油站就算良好出发点，否则就不算。请返回长度为N的boolean型数组res，res[i]代表第i个加油站是不是良好出发点

规定只能按照顺时针走，也就是i只能走到i+1，N只能走到1

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行一个整数N表示加油站数量。
第二行N个整数，表示oil数组。
第三行N个整数，表示dis数组。

输出描述:

输出N个整数。若第i个整数为0表示该位置不是良好出发点，为1表示该位置是良好出发点。

示例1

输入

9
4 2 0 4 5 2 3 6 2
6 1 3 1 6 4 1 1 6

输出

0 0 0 0 0 0 0 0 0

示例2

输入

8
4 5 3 1 5 1 1 9
1 9 1 2 6 0 2 0

输出

0 0 1 0 0 1 0 1

说明

如果车从A点出发，到B点且加上B的油，还剩8的油，发现到不了C；
如果从B点出发，发现车到不了C；
如果从C点出发，发现可以转一圈，所以C点是良好出发点。

备注:

算法知识视频讲解

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, l=0, r=1;
    cin>>n;
    long d[n], a[n], dp[n];
    memset(d, 0, sizeof(d));
    memset(a, 0, sizeof(a));
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++){
        cin>>d[i];
        a[i] -= d[i];
    }
    long t = a[0];
    while(l != r){
        if(t >= 0){
            t += a[r];
            r = (r+1)%n;
        }else{
            l = (l-1+n)%n;
            t += a[l];
        }
    }
    if(t >= 0){
        int k = l;
        for(int i=0;i<n;i++){
            if(t >= 0){
                dp[k] = 1;
                k = (k-1+n)%n;
                t = a[k];
            }else{
                dp[k] = 0;
                k = (k-1+n)%n;
                t += a[k];
            }
        }
    }
    for(int i=0;i<n;i++)
        cout<<dp[i]<<" ";
    return 0;
}

发表于 2020-03-16 22:58:59 回复(1)

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long n;
    cin>>n;
    vector<long>oil(n);
    vector<long>cost(n);
    for(long i=0;i<n;++i) cin>>oil[i];
    for(long i=0;i<n;++i) cin>>cost[i];
    // 每个站能获得的纯能
    for(long i=0;i<n;++i) oil[i]-=cost[i];
    vector<int>ans(n,-1);
    long start = 0;
    long end = 1;
    long rest = oil[0];
    while(start!=end)
    {
        if(rest>=0)  // 向右扩，看是否能到下一个站
        {
            rest += oil[end];
            end = (end+1)%n;
        }
        else  // 向左扩，看上一个站有没有可能补充上现在相差的油量
        {
            start = (start-1+n)%n;
            rest += oil[start];
        }
    }
    if(rest>=0) // 找到一个可行出发点能绕行一周
    {
        long cur = start;
        rest = oil[start];
        while(ans[cur]==-1)
        {
            // 向左找，看上一站能否到达可行点
            if(rest>=0)   // 可达
            {
                ans[cur]=1;
                cur = (cur-1+n)%n; 
                rest = oil[cur]; // 油量置成上一站的
            }
            else  // 不可达
            {
                ans[cur] = 0;
                cur = (cur-1+n)%n;  // 也往左找，寻求可能补充油量的站出现
                rest += oil[cur];
            }

        }
    }
    else   // 绕了一周发现没有可行出发点 （总油量小于跑完全部里程所需的油量）
    {
        long cur = start;
        while(ans[cur]==-1) // 全部置为0
        {
            ans[cur]=0;
            cur = (cur-1+n)%n;
        }
    }
    for(int i:ans)
        cout<<i<<" ";
    return 0;
}

发表于 2020-02-12 17:57:47 回复(1)

骆康骆康

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int length = Integer.parseInt(bf.readLine());
        String[] str1 = bf.readLine().split(" ");
        String[] str2 = bf.readLine().split(" ");
        int[] oil = new int[length];
        int[] dis = new int[length];
        int[] res = new int[length];
        for(int i=0;i<length;i++){
            oil[i] = Integer.parseInt(str1[i]);
            dis[i] = Integer.parseInt(str2[i]);
        }
        long sumoil = 0;
        long sumdis = 0;
        for(int i=0;i<length;i++){
            for(int j=i;j<length+i;j++){
                if(j < length){
                    sumoil += oil[j];
                    sumdis += dis[j];
                }else{
                    sumoil += oil[j-length];
                    sumdis += dis[j-length];
                }
                if(sumoil < sumdis){
                    res[i] = 0;
                    break;
                }else {
                res[i] = 1;
                }
            }
            sumoil = 0;
            sumdis = 0;
        }
        for(int i=0;i<length;i++) {
            System.out.print(res[i]+" ");
        }
    }
}

/*
9
4 2 0 4 5 2 3 6 2
6 1 3 1 6 4 1 1 6

0 0 0 0 0 0 0 0 0

8
4 5 3 1 5 1 1 9
1 9 1 2 6 0 2 0

0 0 1 0 0 1 0 1
*/

发表于 2020-01-21 09:37:21 回复(2)

Java

pein531

这个题用左神的原创方法能够做到时间复杂度O(N)，额外空间复杂度O(1)。整体的流程是一个窗口的扩张，窗口端点不回退。首先，我们需要计算一个纯能值数组（用oil数组的相应元素减去dis数组的相应元素即可，不开辟额外空间，在oil数组上直接进行原地操作）。纯能值数组中的元素oil[i]表示：如果从i位置强行去往下一个位置（假设在接下来的举例中，下一个位置是沿逆时针方向的下一个节点），还剩下多少油。即如果某个元素为负，说明从该位置出发根本无法去往它的下一个节点，如此一来我们就将问题转化成了：求符合“从该位置出发，累加一圈的过程中不出现负数”的所有位置。

如果我们穷举所有为非负数的位置，从它出发开始对数组进行“环绕”，那么算法的时间复杂度就是O(N²)，会超时。用左神的指标最优解来求解这个问题时，需要如下4个变量：

head，表示窗口的头；
tail，表示窗口的尾（开区间，不包括）；
rest，表示从窗口头累加到尾的剩余油量；
need，表示某个位置要到达窗口的头部位置需要的油量。

1.一个没有良好出发点的例子

举个例子来描述算法的过程，假设有ABCDEFGHI节点组成的一个环，找一个非负的节点H出发，head=H，tail=I，rest=5，need=0。H可以逆时针扩张到I，window=[H,A)，rest累加上I的值rest=5-4=1。但很快我们就发现，窗口并不能够把节点A也囊括进来，否则窗口内的rest就为负了。此时窗口没有绕一圈，H不是个良好的出发点。

由于窗口不能逆时针扩张了，接下来我们考虑窗口顺时针方向的G，G接到window的头代价是0，need=0，直接包含进窗口就行，得到窗口window=[G,A)，rest=1+2=3。以G为出发点，再回来考虑窗口能不能逆时针扩，由于rest=3>-2，所以A点可以被纳入窗口，rest=3-2=1。随后窗口把B点包括进来，rest=1+1=2，就无法再往逆时针扩张了，因为rest累加上C点的值会使得rest小于0，此时window=[G,C)。它表示从G出发最远也只能走到B了，G不是个良好的出发点。

逆时针扩不动了，又接着回去看F点，F点是负数，不对它做尝试，直接判定它不是个良好的出发点，need=2（表示要通过F点接到窗口的头—G，需要额外的2容量油）。同理跳过E点来到D点，need=2+1=3。而D刚好有3个油，能够冲到G，窗口变为window=[D,C)。但D到达G时并不能带来更多的油，所以rest仍然为2，窗口还是无法逆时针扩张把C点囊括进来，因此D点也不是个良好的出发点。窗口顺时针到C，因为是负数，所以跳过，而跳过之后就来到了窗口的内部。此时我们已经不需要再检验窗口内的B点是不是个良好的出发点了，它一定不是。因为从G出发，逆时针环绕的极限位置就是到B，也就是说从G出发是可以带着非负的油量到B的，但即便是如此，都没能够突破B到达C，所以光凭B的初始油量是不可能到C点的，更别说它能绕一圈了。

2.一个有良好出发点的例子

下面再举一个有良好出发点的例子，首先随便选一个非负的点A作为初始的出发点

此时head=A，tail=B，rest=3，need=0，显然A无法冲到B，他不是个良好的出发点。然后我们顺时针看H点，它是个非负数，可以无代价地到达A，rest=12，不仅如此，还可以接着逆时针冲。到达B，rest=8；到达C，rest=10；到达D，rest=9；到达E，rest=8；到达F，rest=9；到达G，rest=8>0，已经绕完一圈了，H是个良好的出发点。接下来我们从H顺时针考虑其他的点，此时可以发现，只要这个点能够撑到H点，它就一定能够绕一圈，因此我们只需要考虑H的顺时针方向哪些点的纯能值可以比need大，只要能够负担的起到H的代价，就能够达成绕场一周的壮举。随后，发现F点（能够消耗掉1容量的油冲过G来到H点）和C点（能够消耗2容量的油，通过D点和E点来到F点）都是良好的出发点。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        long[] oil = new long[n];
        for(int i = 0; i < n; i++){
            oil[i] = Long.parseLong(strArr[i]);
        }
        strArr = br.readLine().split(" ");
        long[] dis = new long[n];
        // 先计算纯能值数组
        for(int i = 0; i < n; i++){
            dis[i] = Long.parseLong(strArr[i]);
            oil[i] -= dis[i];
        }
        int head = getStartedPoint(oil);
        if(head == -1){
            for(int i = 0; i < n; i++){
                System.out.print("0 ");
            }
        }else{
            long[] res = solve(oil, head);
            for(int i = 0; i < n; i++){
                System.out.print(res[i] + " ");
            }
        }
    }
    
    private static long[] solve(long[] energy, int head) {
        int n = energy.length;
        long[] res = new long[n];
        int cur = head;
        int tail = nextIndex(head, n);
        long rest = 0, need = 0;
        do{
            if(cur != head && cur == prevIndex(tail, n)){
                break;      // 当前的位置cur已经来到了连通区域中，直接中断循环，可以确定后续的开始点一定无法转完一圈
            }
            if(energy[cur] < need){
                // 当前位置不能连到连通区域的头部，连通区先往尾部方向开始扩
                need -= energy[cur];
            }else{
                rest += energy[cur] - need;
                need = 0;
                // 有剩余的油就往后走
                while(rest >= 0 && cur != tail){
                    rest += energy[tail];
                    tail = nextIndex(tail, n);
                }
                // 如果连通区域已经覆盖整个环，当前的start是良好出发点，进入2阶段
                if(rest >= 0){
                    res[cur] = 1;
                    // 找到所有能到达cur的点，它们全部都是良好出发点
                    connectGood(energy, prevIndex(cur, n), head, res);
                    break;
                }
            }
            cur = prevIndex(cur, n);
        }while(cur != head);
        return res;
    }
    
    private static void connectGood(long[] energy, int start, int init, long[] res) {
        long need = 0;
        while(start != init){
            if(energy[start] < need){
                // 能量不够
                need -= energy[start];
            }else{
                // 能量够，可以到达
                res[start] = 1;
                need = 0;
            }
            start = prevIndex(start, energy.length);
        }
    }
    
    // 获得环中index的前一个位置
    private static int prevIndex(int index, int n) {
        return index == 0? n - 1: index - 1;
    }
    
    // 获得环中index的下一个位置
    private static int nextIndex(int index, int n) {
        return index == n - 1? 0: index + 1;
    }
    
    private static int getStartedPoint(long[] energy) {
        int init = -1;
        for(int i = 0; i < energy.length; i++){
            if(energy[i] >= 0){
                init = i;
            }
        }
        return init;
    }
}

其实把这个思路转化成code难度也很高，需要调试挺长时间，为了能AC还需要考虑累加时的溢出问题。

编辑于 2021-12-09 15:51:06 回复(0)

cs初学者

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        String[] ss1 = br.readLine().trim().split(" ");
        String[] ss2 = br.readLine().trim().split(" ");
        int[] oil = new int[len];
        int[] dis = new int[len];
        for(int i=0;i<len;i++){
            oil[i] = Integer.parseInt(ss1[i]);
            dis[i] = Integer.parseInt(ss2[i]);
        }
        boolean[] res = getRes(oil,dis);
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<res.length;i++){
            int tmp = res[i]?1:0;
            sb.append(tmp+" ");
        }
        System.out.println(sb.toString().trim());
    }
    public static boolean[] getRes(int[] oil,int[] dis){
        if(dis==null||oil==null||dis.length<2||dis.length!=oil.length) return null;  
        int init = init(oil,dis);
        return init==-1?new boolean[dis.length]:enlargeArea(dis,init);        
    }
    public static boolean[] enlargeArea(int[] dis,int init){
        boolean[] res = new boolean[dis.length];
        int start = init;
        int end = nextIndex(init,dis.length);
        long need = 0;
        long rest = 0;
        do{
            //往后扩充已经没法扩充了
            if(start!=init&&start==lastIndex(end,dis.length)){
                break;
            }
            if(dis[start]<need){
                need -= dis[start];
            }else{
                //试着往前进
                rest += dis[start]-need;
                need = 0;
                while(rest>=0&&end!=start){
                    rest += dis[end];
                    end = nextIndex(end,dis.length);
                }
                if(rest>=0){
                    res[start] = true;
                    connectGood(dis,lastIndex(start,dis.length),init,res);
                    break;
                }
            }
            start  = lastIndex(start,dis.length);
        }while(start!=init);
        return res;
    }
    public static void connectGood(int[] dis,int start,int init,boolean[] res){
        long need = 0;
        while(start!=init){
            if(dis[start]<need){
                need -= dis[start];
            }else{
                res[start] = true;
                need = 0;
            }
            start = lastIndex(start,dis.length);
        }
    }
    public static int lastIndex(int init,int size){
        return init==0?size-1:(init-1);
    }
    public static int nextIndex(int init,int size){
        return init==size-1?0:(init+1);
    }
    public static int init(int[] oil,int[] dis){
        int init = -1;
        for(int i=0;i<oil.length;i++){
            dis[i] = oil[i] - dis[i];
            if(dis[i]>=0){
                init = i;
            }
        }
        return init;
    }
}

发表于 2021-09-26 15:53:44 回复(0)

你的爸爸纠

import sys
if __name__ == "__main__":
    line = sys.stdin.readline().rstrip().split(" ")
    N = int(line[0])
    line = sys.stdin.readline().rstrip().split(" ")
    oil = list(map(int, line))
    line = sys.stdin.readline().rstrip().split(" ")
    dis = list(map(int, line))
    delta = []
    res = []
    for i in range(N):
        delta.append(oil[i]-dis[i])
        res.append(0)
    if sum(delta)<0:
        for i in range(N):
            if i <N-1:
                print(0,end=" ")
            else:
                print(0)
    else:
        start = 0
        sum = 0
        travel = 0
        while travel < N:
            sum += delta[(start+travel)%N]
            while sum<0:
                sum += delta[(start-1+N)%N]
                start = (start-1+N)%N
                travel += 1
            travel += 1
        # already get a valid start point
        res[start] = 1
        sum = 0
        for i in range(1,N):
            sum += delta[(start-i+N)%N]
            if sum>=0 and delta[(start-i+N)%N]>0:
                res[(start-i+N)%N] = 1
                sum = 0
        for i in range(N):
            if i <N-1:
                print(res[i],end=" ")
            else:
                print(res[i])

编辑于 2020-04-06 08:23:06 回复(0)

提交观点

问题信息

模拟查找

上传者：小小

难度：

6条回答 20收藏 4706浏览

通过挑战的用户

查看代码

牛客64184...

2022-12-20 18:05:43
牛客89830...

2022-11-12 21:33:20
牛客38404...

2022-11-12 21:32:57
讨个offer

2022-10-08 16:34:56
Keen06

2022-09-01 17:40:24