AcWing 1088. 旅行问题（前缀和单调队列优化dp 破环成链）

题目链接：

1088 旅行问题

思路：

1.破环成链，加上一倍这是常规操作。

2.引用两张图：

顺时针，我们可以倒着遍历，为什么呢，是因为我们可以在倒着遍历的时候处理到后n个的窗口最小值，然后遍历到前n个的时候我们就可以将第i个和窗口最值比较，只要比这个最值小就可以保证环绕一圈

逆时针，注意到有几个不同：

1.首先i点是当前点油量减去到前一个点的距离，那么这里就要考虑到第一个点，就是第n个点到下一个点（第一个点）的距离

2.其实本质是一样的，那么我们就要正着处理，处理到后n个就处理完了前n给的窗口最小值，然后遍历到后n个我们就可以去比较前缀和哪个大判断是不是可以逆时针往回走一圈了

这道题目是这个系列最难理解的我推荐先理解这些题目之后再去做这道题目：

代码：

#include<iostream>
#define int long long
using namespace std;
const int N=2e6+10;
int o[N],d[N],s[N],ok[N],n,q[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>o[i]>>d[i],s[i]=s[i+n]=o[i]-d[i];
    for(int i=1;i<=2*n;i++)s[i]+=s[i-1];
    int hh=0,tt=-1;
    for(int i=2*n;i;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])ok[i]=1;
    }
    hh=0,tt=-1;
    d[0]=d[n];
    for(int i=1;i<=n;i++)s[i]=s[i+n]=o[i]-d[i-1];
    for(int i=2*n;i;i--)s[i]+=s[i+1];
    for(int i=1;i<=2*n;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[i+1]<=s[q[hh]])ok[i-n]=1;
    }
    for(int i=1;i<=n;i++){
        ok[i]?puts("TAK"):puts("NIE");
    }
    
}

for(int i=1;i<=n;i++){
ok[i]?puts(“TAK”):puts(“NIE”);
}

}