AcWing 1088 旅行问题

题目传送门

参考：
https://www.acwing.com/solution/content/12142/
https://www.acwing.com/solution/content/34005/

顺时针

每个点i表示从i点加oil[i]的油再耗dist[i]的油所剩的油量,即oil[i] - dist[i]

1. 计算出油量的前缀和

2. 从某个点i出发，顺时针走一圈，在过程中油量始终 >= 0，等价于在[i,i + n - 1]中，对任意的j,i <= j <= i + n - 1，均有s[j] - s[i - 1] >= 0，即i固定，找s[j]的最小值，即从[i,i + n - 1]中找到滑动窗口的最小值

3. 由于2操作，需要对i进行反向遍历，即从n * 2遍历到1，又由于i <= j <= i + n - 1，遍历到i时需要用到i位置的值，因此找[i,i + n - 1]区间最小值时需要在while后面的语句找

逆时针

每个点i表示从i点加oil[i]的油再耗dist[i - 1]的油所剩的油量,即oil[i] - dist[i - 1]，其中1号点耗的是dist[n]的油，因此需要初始化dist[0] = dist[n]

1. 计算出油量的后缀和

2. 从某个点i出发，逆时针走一圈，在过程中油量始终 >= 0，等价于在[i - n + 1,i]中，对任意的j,i - n + 1 <= j <= i，均有s[j] - s[i + 1] >= 0，即i固定，找s[j]的最小值，即从[i - n + 1,i]中找到滑动窗口的最小值

3. 由于2操作，需要对i进行正向遍历，即从1遍历到n * 2，又由于i - n + 1 <= j <= i，遍历到i时需要用到i位置的值，因此找[i - n + 1,i]区间最小值时需要在while`后面的语句找

#include 

using namespace std;
typedef long long LL;
const int N = 2000010;

int n;
int oil[N], dist[N];
LL s[N];        // 顺时针时表示oil[i]-dist[i]的前缀和，逆时针时表示oil[i]-dist[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++) cin >> oil[i] >> dist[i];
    // 顺时针时求oil[i]-dist[i]的前缀和,这个可以通过画环形图进行深入理解
    for (int i = 1; i <= n; i++) s[i] = s[i + n] = oil[i] - dist[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--) {
        // 判断是否滑出[i,i+n-1]的窗口
        if (hh <= tt && q[hh] > i + n - 1) hh++;
        while (hh <= tt && s[q[tt]] >= s[i]) tt--;
        q[++tt] = i;
        // 此时队头元素就是区间min
        // 表示以i起起始顺时针走有解
        if (i <= n && s[q[hh]] - s[i - 1] >= 0) st[i] = true;//如果从i点出发，那么全程中
    }

    // 逆时针时求oil[i]-dist[i-1]的后缀和
    dist[0] = dist[n]; // oil[1]-dist[0]时需要用到
    for (int i = n; i; i--) s[i] = s[i + n] = oil[i] - dist[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;
        // 注意这里起始位置是i-n+1的前一个位置
        if (i > n && s[q[hh]] - s[i + 1] >= 0) st[i - n] = true;
    }
    //输出
    for (int i = 1; i <= n; i++) puts(st[i] ? "TAK" : "NIE");
    return 0;
}