题目链接

1088. 旅行问题

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

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

\(3 \le n \le 10^6\),
\(0 \le p_i \le 2 \times 10^9\),
\(0 \le d_i \le 2 \times 10^9\)

输入样例：

5
3 1
1 2
5 2
0 1
5 4

输出样例：

TAK
NIE
TAK
NIE
TAK

解题思路

单调队列

如果是顺时针的话将当前油量加上后面要走的距离，这样形成一个数组，题目即要求保证所有的前缀和不小于 \(0\)，不妨破环成链，将数组复制一遍，计算数组前缀，同时维护一个大小为 \(n\) 的滑动窗口，对于 \(1\) 号点，显然在 \(n\) 这个位置判断滑动窗口内的最小值是否小于 \(0\) 即可，滑动窗口往后移动 \(1\) 个单位的时候，不难发现这时滑动窗口的最小值需要减去 \(i-n\) 这个位置的前缀和才是实际上对于 \(2\) 号点的前缀最小值，对于逆时针亦同理

• 时间复杂度：\(O(n)\)

代码

// Problem: 旅行问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1090/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=2e6+5;
int n,q[N],hh,tt;
PII b[N];
LL a[N];
bool res[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&b[i].fi,&b[i].se),a[i]=b[i].fi-b[i].se,a[i+n]=a[i];
    for(int i=1;i<=2*n;i++)
    {
    	a[i]+=a[i-1];
    	while(hh<=tt&&i-q[hh]+1>n)hh++;
    	while(hh<=tt&&a[q[tt]]>=a[i])tt--;
    	q[++tt]=i;
    	if(i>=n&&a[q[hh]]>=a[i-n])res[i-n+1]=true;
    }
    for(int i=1;i<=n;i++)a[i]=b[i].fi-b[i==1?n:i-1].se,a[i+n]=a[i];
    reverse(a+1,a+1+2*n);
    hh=tt=0;
    for(int i=1;i<=2*n;i++)
    {
    	a[i]+=a[i-1];
    	while(hh<=tt&&i-q[hh]+1>n)hh++;
    	while(hh<=tt&&a[q[tt]]>=a[i])tt--;
    	q[++tt]=i;
    	if(i>=n&&a[q[hh]]>=a[i-n])res[n+1-(i-n+1)]=true;
    }
    for(int i=1;i<=n;i++)puts(res[i]?"TAK":"NIE");
    return 0;
}