1088. 旅行问题

John 打算驾驶一辆汽车周游一个环形公路。

公路上总共有 n 个车站，每站都有若干升汽油（有的站可能油量为零），每升油可以让汽车行驶一千米。

John 必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。

在一开始的时候，汽车内油量为零，John 每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。

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

输入格式

第一行是一个整数 n，表示环形公路上的车站数；

接下来 n 行，每行两个整数 pi,di，分别表示表示第 i 号车站的存油量和第 i 号车站到 顺时针方向 下一站的距离。

输出格式

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

数据范围

3≤n≤106,
0≤pi≤2×109,
0≤di≤2×109

输入样例：

5
3 1
1 2
5 2
0 1
5 4

输出样例：

TAK
NIE
TAK
NIE
TAK

思路：

/*
顺时针
每个点i表示从i点加oil[i]的油再耗dist[i]的油所剩的油量,即oil[i] - dist[i]1、计算出油量的前缀和
2、从某个点i出发，顺时针走一圈，在过程中油量始终 >= 0，等价于在[i,i + n - 1]中，对任意的j,i <= j <= i + n - 1，均有s[j] - s[i - 1] >= 0，即i固定，找s[j]的最小值，即从[i,i + n - 1]中找到滑动窗口的最小值
3、由于2操作，需要对i进行反向遍历，即从n * 2遍历到1，又由于i <= j <= i + n - 1，遍历到i时需要用到i位置的值，因此找[i,i + n - 1]区间最小值时需要在while后面的语句找
*/

/*
逆时针
每个点i表示从i点加oil[i]的油再耗dist[i - 1]的油所剩的油量,即oil[i] - dist[i - 1]，其中1号点浩的是dist[n]的油，因此需要初始化dist[0] = dist[n]1、计算出油量的后缀和
2、从某个点i出发，逆时针走一圈，在过程中油量始终 >= 0，等价于在[i - n + 1,i]中，对任意的j,i - n + 1 <= j <= i，均有s[j] - s[i + 1] >= 0，即i固定，找s[j]的最小值，即从[i - n + 1,i]中找到滑动窗口的最小值
3、由于2操作，需要对i进行正向遍历，即从1遍历到n * 2，又由于i - n + 1 <= j <= i，遍历到i时需要用到i位置的值，因此找[i - n + 1,i]区间最小值时需要在while后面的语句找
*/

代码：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N = 2e6 + 10;int n;
int oil[N], dist[N];
LL s[N];
int q[N];
bool st[N];int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> oil[i] >> dist[i];s[i] = s[i + n] = oil[i] - dist[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 >= 1; 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])st[i] = 1;}//逆时针dist[0] = dist[n];for (int i = n; i >= 1; i--)s[i] = s[i + n] = oil[i] - dist[i - 1];for (int i = 2 * n; i >= 1; i--)s[i] += s[i + 1];hh = 0;tt = -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 + 1 && s[q[hh]] >= s[i + 1])st[i - n] = 1;}for (int i = 1; i <= n; i++)if (st[i])puts("TAK");elseputs("NIE");return 0;
}