53 加油站良好出发点问题
Table of Contents

ac

import java.util.*;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    static int mod = 1_000_000_000 + 7;

    static int N = 100_001;

    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        int n = sc.nextInt();
        int[] oil = new int[n];
        for(int i=0;i<n;i++){
            oil[i] = sc.nextInt();
        }
        int[] dis = new int[n];
        for(int i=0;i<n;i++){
            dis[i] = sc.nextInt();
        }
        // 存储结果用
        boolean[] ans = new boolean[N];

        int init = -1; // 任意一个可以走到下一位置的点
        int[] Arr = new int[n]; // 净值
        for(int i=0;i<n;i++){
            Arr[i] = oil[i] - dis[i];
            if(Arr[i] >= 0){
                init = i;
            }
        }
        // 一个都没有
        if(init == -1){
            for(int i=0;i<n-1;i++){
                System.out.print("0 ");
            }
            System.out.println(0);
            return;
        }
        int start = init;
        int end = nextIndex(init, n);
        long need = 0; // 需要的 start -> pos
        long redundance = 0; // 多余的 pos  <-  end
        // 扩充区间 [start ... end)
        do{
            if(start != init && start == lastIndex(end, n)){
                break;
            }
            if(Arr[start] < need){
                need -= Arr[start];
            }else {
                // start到pos位置多出来rest
                redundance += Arr[start] - need;
                need = 0;
                // 不断到往后走  redundance类似Arr的累加和,大于等于0就是可以走到的
                while (redundance >= 0 && end != start){
                    redundance += Arr[end];
                    end = nextIndex(end, n);
                }
                if(redundance >= 0){
                    // 找到一个良好出发点,就直接往前开始一个个处理,要break
                    ans[start] = true;
                    solve(Arr, n, lastIndex(start,n), start, ans);
                    break;
                }
            }
            // 如果start不是良好出发点,就接着找
            start = lastIndex(start, n);
        }while (start != init);
        // print ans
        for(int i=0;i<n-1;i++){
            System.out.print((ans[i] ? "1": "0") + " ");
        }
        System.out.println((ans[n-1] ? "1": "0"));
    }

    static void solve(int[] Arr, int n, int start, int init, boolean[] ans) {
        long need = 0;
        // start不断往前
        while (start != init) {
            if (Arr[start] < need) { // start 走不到 start+1, need需要加;下一次need需要的更多
                need -= Arr[start];
            }else {
                ans[start] = true;
                need = 0;
            }
            start = lastIndex(start, n);
        }
    }

    static int lastIndex(int index,int n){
        return index==0 ? (n-1) : index-1;
    }

    static int nextIndex(int index,int n) {
        return index == (n - 1) ? 0 : index + 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

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
 */

leetcode:134题

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;

        int init = -1; // init表示初始状态时,任意一个可以走到下一位置的点
        int[] Arr = new int[n]; // 净值,>=0 表示有多的, <0表示不够
        for(int i=0;i<n;i++){
            Arr[i] = gas[i] - cost[i];
            if(Arr[i] >= 0){
                init = i;
            }
        }
        if(init == -1){
            return -1;
        }
        int ans = -1;
        int start = init;
        int end = nextIndex(init, n);
        long need = 0; // 需要的 start -> pos
        long redundance = 0; // 多余的 pos  <-  end
        // 扩充区间 [start ... end)
        do{
            // 表示整个结束
            if(start != init && start == lastIndex(end, n)){
                break;
            }
            if(Arr[start] < need){ // 表示不够
                need -= Arr[start];
            }else {
                // start到pos位置多出来rest
                redundance += Arr[start] - need;
                need = 0;
                // 不断到往后走  redundance类似Arr的累加和,大于等于0就是可以走到的
                while (redundance >= 0 && end != start){
                    redundance += Arr[end];
                    end = nextIndex(end, n);
                }
                if(redundance >= 0){
                    // 找到一个良好出发点,就直接往前开始一个个处理,要break
                    ans = start;
                    break;
                }
            }
            // 如果start不是良好出发点,start往前,接着找
            start = lastIndex(start, n);
        }while (start != init);
        return ans;
    }

    public int lastIndex(int index,int n){
        return index==0 ? (n-1) : index-1;
    }

    public int nextIndex(int index,int n) {
        return index == (n - 1) ? 0 : index + 1;
    }

}