acwing-1088旅行问题

全栈程序员站长

发布于 2022-09-22 12:32:07

2660

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

原题链接 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 输入样例：

输出样例：

TAK
NIE
TAK
NIE
TAK

单调队列

#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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

https