AcWing 1088. 旅行问题

John 打算驾驶一辆汽车周游一个环形公路。

公路上总共有 n个车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。

John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。

在一开始的时候，汽车内油量为零，John每到一个车站就把该站所有的油都带上（起点站亦是如此），
行驶过程中不能出现没有油的情况。

任务：判断以每个车站为起点能否按条件成功周游一周。

输入格式
第一行是一个整数 n，表示环形公路上的车站数；

接下来 n行，每行两个整数 p_i,d_i，分别表示表示第 i号车站的存油量和第 i号车站到顺时针方向 下一站的距离。

输出格式
输出共 n行，如果从第 i号车站出发，一直按顺时针（或逆时针）方向行驶，能够成功周游一圈，
则在第 i行输出 TAK，否则输出 NIE。

数据范围
3≤n≤10^6
0≤pi≤2×10^9
0≤di≤2×10^9

5
3 1
1 2
5 2
0 1
5 4

NIE
TAK
NIE
TAK

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 2000010;

int n;
int p[N], d[N];
LL s[N]; // 顺时针时表示p[i]-d[i]的前缀和，逆时针时表示p[i]-d[i-1]的后缀和
int q[N]; // 单调队列维护长度为n的区间中s[i]的最小值
bool st[N]; // st[i]为true表示从i开始有解

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d%d", &p[i], &d[i]);

    // 顺时针时求p[i]-d[i]的前缀和
    for (int i = 1; i <= n; i++) s[i] = s[i + n] = p[i] - d[i];
    for (int i = 1; i <= n * 2; i++) s[i] += s[i - 1];
    // 从大到小枚举i，然后考虑区间[i,i+n-1]中的最小值是否>=s[i-1]
    int hh = 0, tt = -1;
    for (int i = n * 2; i; i--) {
        if (hh <= tt && q[hh] > i + n - 1) hh++; // 判断是否滑出[i,i+n-1]的窗口
        while (hh <= tt && s[q[tt]] >= s[i]) tt--;
        q[++tt] = i;
        // 此时队头元素就是区间min
        if (i <= n && s[q[hh]] >= s[i - 1]) st[i] = true; // 表示以i起起始顺时针走有解
    } 

    // 逆时针时求p[i]-d[i-1]的后缀和
    d[0] = d[n]; // p[1]-d[0]时需要用到
    for (int i = n; i; i--) s[i] = s[i + n] = p[i] - d[i - 1];
    for (int i = n * 2; i; i--) s[i] += s[i + 1];
    // 从小到大枚举i，然后考虑区间[i-n+1,i]中的最小值是否>=s[i+1]
    hh = 0, tt = -1;
    for (int i = 1; i <= n * 2; i++) {
        if (hh <= tt && q[hh] < i - n + 1) hh++;
        while (hh <= tt && s[q[tt]] >= s[i]) tt--;
        q[++tt] = i;
        if (i > n && s[q[hh]] >= s[i + 1]) st[i - n] = true; // 注意这里起始位置是i-n+1的前一个位置
    }
    for (int i = 1; i <= n; i++) puts(st[i] ? "TAK" : "NIE");

    return 0;
}