旅行问题

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
");else printf("NIE
");
}