首页
登录 | 注册

[单调队列]旅行问题

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

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

输入 第一行是一个整数 n ,表示环形公路上的车站数;

接下来 n 行,每行两个整数 pi,dipi,di,分别表示表示第 ii 号车站的存油量和第ii号车站到下一站的距离。

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

样例输入
5
3 1
1 2
5 2
0 1
5 4
样例输出
TAK
NIE
TAK
NIE
TAK
提示
对于全部数据,3≤n≤1e6,0≤pi≤2×1e9,0<di≤2×1e9

分析:
典型的单调队列题,拆环为链,并复制一遍
将点权和边权相减得到一个a数组,并对其求前缀和,则一个位置上一个位置的前缀和若大于这个位置及其后面n个位置中任意一个前缀和的话这个位置就不可行
则问题转化为快速判断一列数中的最小值,直接上ST表
另外本题还有单调队列做法:

代码(单调队列):

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000005;
const int inf=0x7ffff;
int n,m;
ll ans[N],pos[N],f[N],sum[N],p[N],d[N];
deque <int> q;
inline void check() {
    for(int i=1;i<=m;++i) sum[i]=sum[i-1]+f[i];
    for(int i=1;i<=m;++i){
        while(!q.empty() && sum[q.back()]>sum[i]) q.pop_back();
        q.push_back(i);
        while(q.front()<i-n+1) q.pop_front();
        if(i>=n && sum[q.front()]-sum[i-n]>=0) ans[pos[i-n+1]]|=1;
    }
}
int main() {
	cin>>n;m=n<<1;
    for(int i=1;i<=n;++i) scanf("%lld%lld",&p[i],&d[i]);
    for(int i=1;i<=n;++i) f[i]=f[i+n]=p[i]-d[i],pos[i]=pos[i+n]=i;
    check();
    int cnt=1;
    f[cnt]=f[cnt+n]=p[1]-d[n];
    pos[cnt]=pos[cnt+n]=1;
    for(int i=n;i>=2;--i){
        cnt++;
        f[cnt]=f[cnt+n]=p[i]-d[i-1];
        pos[cnt]=pos[cnt+n]=i;
    }
    check();
    for(int i=1;i<=n;++i) {
        if(ans[i]) printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}


2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.008 s.
京ICP备10005923号