acwing-1088旅行问题

acwing-1088旅行问题原题链接John 打算驾驶一辆汽车周游一个环形公路。公路上总共有 n 个车站,每站都有若干升汽油(有的站可能油量为零),每升油可以让汽车行驶一千米。John 必须从某个车站出发,一直按顺时针(或逆时针)方向走遍所有的车站,并回到起点。在一开始的时候,汽车内油量为零,John 每到一个车站就把该站所有的油都带上(起点站亦是如此),行驶过程中不能出现没有油的情况。任务:判断以每个车站为起点能否按条件成功周游一周。输入格式第一行是一个整数 n,表示环形公路上的车站数;接下来 n 行,每行两个整数

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接
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

单调队列

#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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168516.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 11.1 LAMP架构介绍11.2 MySQL_MariaDB介绍11.3-11.5 MySQL安装

    11.1 LAMP架构介绍11.2 MySQL_MariaDB介绍11.3-11.5 MySQL安装

  • RBF(径向基)神经网络

    RBF(径向基)神经网络

    2021年11月20日
  • 宝塔搭建php项目是什么_用宝塔怎么修改网站源码

    宝塔搭建php项目是什么_用宝塔怎么修改网站源码宝塔搭建PHP项目宝塔下载地址我选的是linux用宝塔搭建前提是你买的服务器并没有安装任何的镜像与环境进入官网选择你要的然后点击立即安装进入安装教程安装要求根据自己的主机商进入,我的是阿里云的设置一些开放端口添加安全组规则添加这些必要的端口mysql3306的记住一定要放行,这样可用本地工具连接远程服务器的数据库上面设置好之后就可以安装了,我的是Centosyuminstall-ywget&&wget-Oin

  • android系统的官网下载地址,Android安卓10.0系统官方正式版

    android系统的官网下载地址,Android安卓10.0系统官方正式版Android安卓10.0系统官方正式版:这是一款关于安卓的系统,没错就在今天,谷歌更新了关于安卓10.0的系统更新,相信很多的小伙伴都应该是不清楚的,应为感觉还是有很多的用户在等着系统自己的更新,没有操心这一方面的事情。Android安卓10.0系统官方正式版更新了什么功能?1、目前来看的话,更新功能还是蛮多的,但是用户能够看的上的就不言而喻;2、毕竟以前放出来的消息就是这一次更新将会有可能安卓…

  • 群晖linux怎么进入u盘,黑群晖菜鸟安装教程(一)制作U盘引导及软洗白!

    群晖linux怎么进入u盘,黑群晖菜鸟安装教程(一)制作U盘引导及软洗白!教程多都是参考网络上的一些大师们的教程做一些简化和把一些要点易出错的地方给大家指出,让大家能更快加入到群晖一起折腾。什么是黑群晖最简单的理解就是用普通的PC机安装了群晖NAS系统让普通的PC机可以体验白群晖的大多数功能。黑群晖对电脑的要求很低最是一般要求CPU为64位不然安装不了的。而且一般我们采用的PC机为低功率集成CPU的ITX主板。常用的主板有集成CPUD525E-240等低功率主板在正…

  • IOS私人API用法

    IOS私人API用法

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号