当前位置: 首页 > news >正文

AcWing 4957:飞机降落

【题目来源】
https://www.acwing.com/problem/content/4960/

【题目描述】
有 N 架飞机准备降落到某个只有一条跑道的机场。
其中第 i 架飞机在 Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di 个单位时间,即它最早可以于 Ti 时刻开始降落,最晚可以于 Ti+Di 时刻开始降落。
降落过程需要 Li 个单位时间。
一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。

【输入格式】
输入包含多组数据。
第一行包含一个整数 T,代表测试数据的组数。
对于每组数据,第一行包含一个整数 N。
以下 N 行,每行包含三个整数:Ti,Di 和 Li。

【输出格式】
对于每组数据,输出 YES 或者 NO,代表是否可以全部安全降落。

【数据范围】
对于 30% 的数据,N≤2。
对于 100% 的数据,1≤T≤10,1≤N≤10,0≤Ti,Di,Li≤105。

【输入样例】
2

3
0 100 10
10 10 10
0 2 20

3
0 10 20
10 10 20
20 10 20


【输出样例】
YES
NO

【样例解释】
对于第一组数据,可以安排第 3 架飞机于 0 时刻开始降落,20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落,30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落,40 时刻完成降落。
对于第二组数据,无论如何安排,都会有飞机不能及时降落。

【算法分析】
由数据范围反推算法复杂度以及算法内容,参见:

https://www.acwing.com/blog/content/32/

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=12;
struct node {int T,D,L;
} p[maxn];bool st[maxn];
int n;bool dfs(int idx, int time) {if(idx==n) return true;for(int i=0; i<n; i++) {if(!st[i]) {if(time<=p[i].T+p[i].D) {st[i]=true;if(dfs(idx+1,max(p[i].T,time)+p[i].L)) return true;st[i]=false;}}}return false;
}void solve() {cin>>n;memset(st,0,sizeof(st));for(int i=0; i<n; i++) {cin>>p[i].T>>p[i].D>>p[i].L;}if(dfs(0,0)) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}int main() {int T;cin>>T;while(T--) {solve();}return 0;
}/*
in:
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20out:
YES
NO
*/





【参考文献】
https://www.acwing.com/solution/content/183838/
https://www.acwing.com/blog/content/32/





 

相关文章:

AcWing 4957:飞机降落

【题目来源】https://www.acwing.com/problem/content/4960/【题目描述】 有 N 架飞机准备降落到某个只有一条跑道的机场。 其中第 i 架飞机在 Ti 时刻到达机场上空&#xff0c;到达时它的剩余油料还可以继续盘旋 Di 个单位时间&#xff0c;即它最早可以于 Ti 时刻开始降落&…...

强化学习研究 PG

由于一些原因&#xff0c; 需要学习一下强化学习。用这篇博客来学习吧&#xff0c; 用的资料是李宏毅老师的强化学习课程。 深度强化学习(DRL)-李宏毅1-8课&#xff08;全&#xff09;_哔哩哔哩_bilibili 这篇文章的目的是看懂公式&#xff0c; 毕竟这是我的弱中弱。 强化…...

uniapp微信小程序 401时重复弹出登录弹框问题

APP.vue 登陆成功后&#xff0c;保存登陆信息 if (res.code 200) {uni.setStorageSync(loginResult, res)uni.setStorageSync(token, res.token);uni.setStorageSync(login,false);uni.navigateTo({url: "/pages/learning/learning"}) }退出登录 toLogout: func…...

Cloud Studio实战——热门视频Top100爬虫应用开发

最近Cloud Studio非常火&#xff0c;我也去试了一下&#xff0c;感觉真的非常方便&#xff01;我就以Python爬取B站各区排名前一百的视频&#xff0c;并作可视化来给大家分享一下Cloud Studio&#xff01;应用链接&#xff1a;Cloud Studio实战——B站热门视频Top100爬虫应用开…...

php 去除二维数组重复

在 PHP 中&#xff0c;我们常常需要对数组进行处理和操作。有时候&#xff0c;我们需要去除数组中的重复元素&#xff0c;这里介绍一种针对二维数组的去重方法。 以下是列举一些常见的方法&#xff1a; 方法一&#xff1a;使用 array_map 和 serialize 函数 array_map 函数可以…...

玩转graphQL

转载至酒仙桥的玩转graphQL - SecPulse.COM | 安全脉搏 前言 在测试中我发现了很多网站开始使用GraphQL技术&#xff0c;并且在测试中发现了其使用过程中存在的问题&#xff0c;那么&#xff0c;到底GraphQL是什么呢&#xff1f;了解了GraphQL后能帮助我们在渗透测试中发现哪些…...

神经网络super(XXX, self).__init__()的含义

学习龙良曲老师的课程&#xff0c;在77节有这样一段代码 import torch from torch import nnclass Lenet5(nn.Module):def __init__(self):super(Lenet5,self).__init__()那么&#xff0c;super(XXX, self).init()的含义是什么&#xff1f; Python中的super(Net, self).init()…...

45.杜芬方程解仿真解曲线(matlab程序)

1.简述 Dufing方程是一种重要的动力系统山&#xff0c;是反映工程物理系统中非线性现象和混沌动力学行为的极其重要的方程式。通过Duffing方程可以探讨铁磁谐振电路中的分岔、拟周期运动、子谐波振荡。而在非线性与混沌系统的研究中&#xff0c;Duffing方程展示了丰富的混沌动力…...

服务器数据恢复-EXT3分区误删除邮件的数据恢复案例

服务器数据恢复环境&#xff1a; 一台服务器有一组由8块盘组建的RAID5阵列&#xff0c;EXT3文件系统。 服务器故障&#xff1a; 由于工作人员的误操作导致文件系统中的邮件丢失。用户需要恢复丢失的邮件数据。 服务器数据恢复过程&#xff1a; 1、将故障服务器中所有磁盘以只…...

C 语言的逗号运算符

逗号运算符 comma operator 逗号运算符最常用在 for 循环的循环头中. 程序示例&#xff1a; #include<stdio.h> #define FIRST_OZ 46 #define NEXT_OZ 20int main(void) {int ounces;float cost;printf("ounces cost\n");for (ounces 1, cost FIRST_OZ…...

无人车沿着指定线路自动驾驶与远程控制的实践应用

有了前面颜色识别跟踪的基础之后&#xff0c;我们就可以设定颜色路径&#xff0c;让无人车沿着指定线路做自动驾驶了&#xff0c;视频&#xff1a;PID控制无人车自动驾驶 有了前几章的知识铺垫&#xff0c;就比较简单了&#xff0c;也是属于颜色识别的一种应用&#xff0c;主要…...

C++ 多态性——纯虚函数与抽象类

抽象类是一种特殊的类&#xff0c;它为一个类族提供统一的操作界面。抽象类是为了抽象和设计的目的而建立的。可以说&#xff0c;建立抽象类&#xff0c;就是为了通过它多态地使用其中的成员函数。抽象类处于类层次的上层&#xff0c;一个抽象类自身无法实例化&#xff0c;也就…...

小程序如何使用防抖和节流?

防抖&#xff08;Debounce&#xff09;和节流&#xff08;Throttle&#xff09;都是用来优化函数执行频率的技术&#xff0c;特别在处理用户输入、滚动等频繁触发的情况下&#xff0c;它们可以有效减少函数的执行次数&#xff0c;从而提升性能和用户体验。但它们的工作方式和应…...

计算机三级网络技术(持续更新)

BGP考点 A S&#xff1a;自治系统 BGP: Border Gateway Protocol&#xff08;当前使用的版本是 BGP-4&#xff09;外部网关协议 动态路由协议可以按照工作范围分为IGP以及EGP。IGP工作在同一个AS内&#xff0c;主要用来发现和计算路由&#xff0c;为AS内提供路由信息的交换&…...

Django Rest_Framework(二)

文章目录 1. http请求响应1.1. 请求与响应1.1.1 Request1.1.1.1 常用属性1&#xff09;.data2&#xff09;.query_params3&#xff09;request._request 基本使用 1.1.2 Response1.1.2.1 构造方式1.1.2.2 response对象的属性1&#xff09;.data2&#xff09;.status_code3&…...

Kotlin~Visitor访问者模式

概念 将数据结构和操作分离&#xff0c;使操作集合可以独立于数据结构变化。 角色介绍 Visitor&#xff1a;抽象访问者&#xff0c;为对象结构每个具体元素类声明一个访问操作。Element&#xff1a;抽象元素&#xff0c;定义一个accept方法ConcreteElement&#xff1a;具体元…...

LVS-DR模式集群构建过程演示

一、工作原理 LVS的工作原理 1.当用户向负载均衡调度器&#xff08;Director Server&#xff09;发起请求&#xff0c;调度器将请求发往至内核空间 2.PREROUTING链首先会接收到用户请求&#xff0c;判断目标IP确定是本机IP&#xff0c;将数据包发往INPUT链 3.IPVS是工作在IN…...

UML-A 卷-知识考卷

UML-A 卷-知识考卷 UML有多少种图&#xff0c;请列出每种图的名字&#xff1a; 常用的几种UML图&#xff1a; 类图&#xff08;Class Diagram&#xff09;&#xff1a;类图是描述类、接口、关联关系和继承关系的图形化表示。它展示了系统中各个类之间的静态结构和关系。时序…...

BpBinder与PPBinder调用过程——Android开发Binder IPC通信技术

在Android系统中&#xff0c;进程间通信&#xff08;IPC&#xff09;是一个非常重要的话题。Android系统通过Binder IPC机制实现进程间通信&#xff0c;而Binder IPC通信技术则是Android系统中最为重要的进程间通信技术之一。本文将介绍Binder IPC通信技术的原理&#xff0c;并…...

篇十五:模板方法模式:固定算法的步骤

篇十五&#xff1a;"模板方法模式&#xff1a;固定算法的步骤" 设计模式是软件开发中的重要知识&#xff0c;模板方法模式&#xff08;Template Method Pattern&#xff09;是一种行为型设计模式&#xff0c;用于定义一个算法的骨架&#xff0c;将算法中一些步骤的具…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...