题目描述

环形问题，距离起点长度为n（顺时针和逆时针两个方向）的路径是否能满足提供的油大于每一段油的消耗。
顺时针的时候，我们把s[i]定义成为第i点加油站提供的油到第i + 1点这段路上消耗油的差值
逆时针的时候，我们把s[i]定义成为第i点加油站提供的油到第i - 1点这段路上消耗油的差值
相当于在2 * N 长度的链上找一个从i开始的，长度为n的存在油耗量的最小值，利用前缀和记录信息，单调队列保存这段区间的最小值，如果在这段区间的前缀和的最小值s[x] 小于这段区间起始点之前那个点的前缀和，则无法完成一圈

时间复杂度

使用队列和前缀和，复杂度O(n)

参考文献

算法提高课

JAVA 代码

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.Deque;
import java.util.ArrayDeque;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author PeterAn lost-th@live.com
 */
public class Main {
    public static void main(String[] args) {// 这个由CHelper自动生成，忽略
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AcWing1088 solver = new AcWing1088();
        solver.solve(1, in, out);
        out.close();
    }

    static class AcWing1088 { 
        static final int N = 2000010;
        static int[] p = new int[N];
        static int[] d = new int[N];
        static long[] s = new long[N];
        static boolean[] vis = new boolean[N];

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            for (int i = 1; i <= n; i++) {
                p[i] = in.nextInt();
                d[i] = in.nextInt();
            }
            for (int i = 1; i <= n; i++) s[i] = s[i + n] = p[i] - d[i];
            // s[i] 定义为从i到i + 1后剩下的油量
            for (int i = 1; i <= n + n; i++) s[i] += s[i - 1]; 
            // 前缀和，把从i到i + 1的耗油量放在s[i]的位置
            Deque<Integer> q = new ArrayDeque<>();
            for (int i = 1; i <= n + n + 1; i++) { 
            // 因为计算i的时候，是从 i - n 到 i ，所以 i = n * 2 + 1 的位置是计算以n为起始的顺时针环
                if (i > n) { // 因为把到达i的油量放在了i - 1的位置，所以到i的位置先判断
                    if (s[i - n - 1] <= s[q.peekFirst()]) vis[i - n] = true;
                }
                // 根据前缀和的定义，如果区间内的最小值大于i - n - 1这个位置的前缀和，那么这个长度为n的区间的油量是够用的
                if (q.size() > 0 && q.peekFirst() < i - n) q.removeFirst(); // 弹出超出范围的元素
                while (q.size() > 0 && s[q.peekLast()] >= s[i]) q.removeLast(); // 保证队列单调
                q.addLast(i);
            }

            d[0] = d[n];
            s[n + n + 1] = 0;
            for (int i = 1; i <= n; i++) s[i] = s[i + n] = p[i] - d[i - 1]; //把从i到i-1的耗油量放在s[i]的位置
            for (int i = n + n; i >= 1; i--) s[i] += s[i + 1]; 
            Deque<Integer> q1 = new ArrayDeque<>();
            for (int i = n + n; i >= 0; i--) {//为把到达i的油量计算放在了i + 1的位置，所以到i的位置先判断
                if (i <= n) {
                    if (s[i + n + 1] <= s[q1.peekFirst()]) vis[i] = true;
                }
                if (q1.size() > 0 && q1.peekFirst() > i + n) q1.removeFirst();
                while (q1.size() > 0 && s[q1.peekLast()] >= s[i]) q1.removeLast();
                q1.addLast(i);
            }
            for (int i = 1; i <= n; i++) {
                if (vis[i]) out.println("TAK");
                else out.println("NIE");
            }
        }

    }

    static class InputReader { // JAVA高速读入类
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream inputStream) {
            reader = new BufferedReader(new InputStreamReader(inputStream));
            tokenizer = new StringTokenizer("");
        }

        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!tokenizer.hasMoreElements()) {
                String nextLine = innerNextLine();
                if (nextLine == null) return false;
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }

        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}