题目链接：http://acm.ocrosoft.com/problem.php?cid=1615&pid=15

题目描述：

John打算驾驶一辆汽车周游一个环形公路。公路上总共有n车站，每站都有若干升汽油（有的站可能油量为0），每升油可以让汽车行驶一千米。John必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为0，John每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。

任务：判断以每个车站为起点能否按条件成功周游一周。

输入

第一行是一个整数n(3<=n<=1000000)，表示环形公路上的车站数。接下来n行，每行两个整数。第i+1行含有：pi（0<=pi<=2000000000），表示第i号车站的存油量；di（0<di<=2000000000），表示第i号车站到下一站的距离。

输出

输出共n行，如果从第i号车站出发，一直按顺时针（或逆时针）方向行驶，能够成功周游一圈，则在第i行输出“TAK”，否则输出“NIE”。

样例输入：

5
3 1
1 2
5 2
0 1
5 4

样例输出：

TAK
NIE
TAK
NIE
TAK

思路：

将p[i]和d[i]相减得到一个quanzhi[i]，并对其求前缀和sum[i]，则一个位置上一个位置的前缀和若大于这个位置及其后面n个位置中任意一个前缀和的话这个位置就不可行。

于是题目转换为单调队列求区域内最小值

 

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 2000005
int n;
ll a[maxn], pos[maxn], quanzhi[maxn], sum[maxn], p[maxn], d[maxn];
deque <int> kong;
void judge()
{
	for (int i = 1; i <= 2 * n; i++)
	{
		sum[i] = sum[i - 1] + quanzhi[i];//sum数组是记录从固定某点开始，到之后每个点还剩下的油，化链为环
	}
	for (int i = 1; i <= 2 * n; i++) //单调队列跑一遍，去除冗杂
	{
		while (!kong.empty() && sum[kong.back()] > sum[i])//保持队列的单调性,等价在找长度为n的区域里的最小值
		{
			kong.pop_back();
		}
		kong.push_back(i);
		if (kong.front() < i - n + 1)//位置过远，数据无效，直接弹掉
		{
			kong.pop_front();
		}
		if (i >= n && sum[kong.front()] - sum[i - n] >= 0)
		{
			a[pos[i - n + 1]] = 1;
		}
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> p[i] >> d[i];
	}
	for (int i = 1; i <= n; i++)
	{
		quanzhi[i] = quanzhi[i + n] = p[i] - d[i];//每个点的油量减去到下一个点的距离，f[i]=f[i+n]的原因是要拆环为链，用一个足够长的链达到环的效果
		pos[i] = pos[i + n] = i;//这个很好理解，拆环为链，位置会有周期的重复
	}
	judge();//正的方向跑一遍
	//反方向处理
	int fan = 1;
	quanzhi[fan] = quanzhi[fan + n] = p[1] - d[n];//反方向起点的初始化
	pos[fan] = pos[fan + n] = 1;//反方向起点的初始化
	for (int i = n; i >= 2; i--) {
		fan++;//起点跑过了，换下一个点
		quanzhi[fan] = quanzhi[fan + n] = p[i] - d[i - 1];//和正方向的处理方式类似
		pos[fan] = pos[fan + n] = i;
	}
	judge();//反的方向跑一遍
	for (int i = 1; i <= n; i++) {
		if (a[i])//如果从i点能跑通
		{
			printf("TAK\n");
		}
		else//如果从i点不能跑通
		{
			printf("NIE\n");
		}
	}
	return 0;
}