旅行问题

单调队列优化DP

原题链接

题目描述：

给定一个环，环上每个节点有一个油量，当车开到这个节点时可以获得该点的油量，该点还有一个值di表示车从i点开到i+1点所耗费的油量，现有一辆车想从任一起点出发，初始可以获得起点的油量，可以选择顺时针走一圈或逆时针走一圈，行驶过程中没油不行，问能否完成环球旅行

分析

先将环拆成链

顺时针

假设a[i]表示点i在i点加了油之后再减去到达下一站所需的耗油量剩余的油量，即w[i]-d[i]
从点i出发，能走一圈的前提是任意时刻剩余的油量>=0 ，等价于在[i,i+n-1]中，对任意j，i<=j<=i+n-1，均有s[j]-s[i-1]>=0,即找到最小的s[j]，若最小的s[j]都满足条件，则i一定可以走一圈回到起点，即在[i,i+n-1]窗口中找到最小值，

逆时针

道理相同，方向相反，求后缀和，对[i-n+1,i]窗口中的最小值s[j]，有s[j]-s[i+1]>=0即可

Code

#include <iostream>
#include <cstring>

using ll = long long;

const int N = 1e6 + 5;

int w[N], d[N];
int q[N];
ll s[N << 1];
bool success[N];

int main() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i ++ ) std::cin >> w[i] >> d[i];
    
    // 顺时针
    for (int i = 1; i <= n; i ++ ) s[i] = s[i + n] = w[i] - d[i];
    for (int i = 1; i <= n * 2; i ++ ) s[i] += s[i - 1];
    
    int hh = 0,tt = -1;
    for (int i = n * 2; i >= 1; i --) {
        if (hh <= tt && q[hh] > i + n - 1) hh ++;
        while(hh <= tt && s[q[tt]] >= s[i]) tt --;
        q[++ tt] = i;
        // 只做i<=n时的即可
        if (i <= n && s[q[hh]] - s[i - 1] >= 0) success[i] = true;
    }
    
    // 逆时针
    d[0] = d[n];
    for (int i = 1; i <= n; i ++ ) s[i] = s[i + n] = w[i] - d[i - 1];
    for (int i = n * 2; i >= 1; i -- ) s[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时的即可
        if (i > n && s[q[hh]] - s[i + 1] >= 0) success[i - n] = true;
    }
    
    for (int i = 1; i <= n; i ++ ) puts(success[i] ? "TAK" : "NIE");
    return 0;
}