先找到一个良好出发点
良好出发点往前,看前面的点是否能走到良好出发点
oil - dis
为净值,大于等于0就能到下一个点,否则不能到
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 */
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; } }