旅行问题

https://loj.ac/problem/10178

题目描述

  环形公路上有\(n\)个车站，每个车站有一定的油量，\(John\)想从第\(i\)个车站出发绕公路一圈，经过每个车站时会带上车站里所有的油，求能否从第\(i\)个车站出发完成周游。

思路

  这题显然有我们\(O(N)\)解决问题，因此我们不能暴力枚举从第\(i\)个点出发，我们可以考虑先把环转化为链，再考虑子状态之间的重叠问题。首先我们可以直接预处理出经过到达每个车站的消耗油量，定义\(sum[i]\)为消耗油量的前缀和，那么题目的要求就是保证任意时刻这个值都要为正，所以我们就是要满足对于\(\forall sum[i]\in [i-n,i]\)值都大于\(0\)，显然我们只需要其中的最小值就可以了，所以我们可以用单调队列维护这个值，那么就可实现\(O(1)\)的判断。需要注意题目并未规定初始方向，所以要两个方向都做一次。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;

ll read()
{
    ll res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res*w;
}

ll a[N],b[N],sum[N],q[N],pos[N];
bool ans[N];
int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read(),b[i]=read();
        a[i+n]=a[i];b[i+n]=b[i];
    }
    for(int i=1;i<=n*2;i++)
        sum[i]=sum[i-1]+a[i-1]-b[i-1];
    int head=0,tail=0;
    for(int i=1;i<=n;i++)
    {
        while(head<=tail&&q[tail]>=sum[i])tail--;
        q[++tail]=sum[i];pos[tail]=i;
    }
    for(int i=n+1;i<=n*2;i++)
    {
        while(head<=tail&&abs(pos[head]-i)>=n)head++;
        ans[i-n]=q[head]-sum[i-n]>=0;
        while(head<=tail&&q[tail]>=sum[i])tail--;
        q[++tail]=sum[i];pos[tail]=i;
    }
    memset(sum,0,sizeof(sum));
    head=0;tail=0;
    for(int i=n*2;i>=1;i--)
        sum[i]=sum[i+1]+a[i+1]-b[i];
    for(int i=n*2;i>n;i--)
    {
        while(head<=tail&&q[tail]>=sum[i])tail--;
        q[++tail]=sum[i];pos[tail]=i;
    }
    for(int i=n;i>=1;i--)
    {
        while(head<=tail&&abs(pos[head]-i)>=n)head++;
        ans[i]|=q[head]-sum[i+n]>=0;
        while(head<=tail&&q[tail]>=sum[i])tail--;
        q[++tail]=sum[i];pos[tail]=i;
    }
    for(int i=1;i<=n;i++)
        if(ans[i])printf("TAK\n");else printf("NIE\n");
}