大家好，又见面了，我是你们的朋友全栈君。
原题链接 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 输入样例：
代码语言：javascript复制5
3 1
1 2
5 2
0 1
5 4输出样例：
代码语言：javascript复制TAK
NIE
TAK
NIE
TAK单调队列
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int N = 3e6 10;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int q[N],hh = 0,tt = 0;
int c[N],l[N];
ll sl[N];
int rl[N];
ll rsl[N];
bool res[N];
int main(){
int n;
cin>>n;
int x,y;
for(int i = 1;i <= n;i ){
cin>>c[i]>>l[i];
rl[i 1] = l[i];
}
rl[1] = rl[n 1];
for(int i = 1;i <= n;i )sl[i] = sl[i - 1] c[i] - l[i];
for(int i = n 1;i <= 2 * n;i )sl[i] = c[i - n] - l[i - n] sl[i - 1];
for(int i = 1;i <= n;i )rsl[i] = rsl[i - 1] c[n - i 1] - rl[n - i 1];
for(int i = n 1;i <= 2 * n;i )rsl[i] = rsl[i - 1] c[n - (i - n - 1)] - rl[n - (i - n - 1)];
for(int i = 1;i <= 2 * n;i ){
if(hh < tt && q[hh] <= i - n)hh ;
while(hh < tt && sl[q[tt - 1]] >= sl[i])tt --;
q[tt ] = i;
if(i >= n && i <= 2 * n - 1){
if(sl[q[hh]] - sl[i - n] >= 0)res[i 1 - n] |= true;
else res[i 1 - n] = false;
}
}
hh = tt = 0;
for(int i = 1;i <= 2 * n;i ){
if(hh < tt && q[hh] <= i - n)hh ;
while(hh < tt && rsl[q[tt - 1]] >= rsl[i])tt --;
q[tt ] = i;
if(i >= n && i <= 2 * n - 1){
if(rsl[q[hh]] - rsl[i - n] >= 0)res[2 * n - i] |= true;
else res[2 * n - i] |= false;
}
}
for(int i = 1;i <= n;i ){
if(res[i])cout<<"TAK"<<endl;
else cout<<"NIE"<<endl;
}
system("pause");
return 0;
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168516.html原文链接：https://javaforall.cn
