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 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di 个单位时间,即它最早可以于 Ti 时刻开始降落&…...
强化学习研究 PG
由于一些原因, 需要学习一下强化学习。用这篇博客来学习吧, 用的资料是李宏毅老师的强化学习课程。 深度强化学习(DRL)-李宏毅1-8课(全)_哔哩哔哩_bilibili 这篇文章的目的是看懂公式, 毕竟这是我的弱中弱。 强化…...
uniapp微信小程序 401时重复弹出登录弹框问题
APP.vue 登陆成功后,保存登陆信息 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非常火,我也去试了一下,感觉真的非常方便!我就以Python爬取B站各区排名前一百的视频,并作可视化来给大家分享一下Cloud Studio!应用链接:Cloud Studio实战——B站热门视频Top100爬虫应用开…...
php 去除二维数组重复
在 PHP 中,我们常常需要对数组进行处理和操作。有时候,我们需要去除数组中的重复元素,这里介绍一种针对二维数组的去重方法。 以下是列举一些常见的方法: 方法一:使用 array_map 和 serialize 函数 array_map 函数可以…...
玩转graphQL
转载至酒仙桥的玩转graphQL - SecPulse.COM | 安全脉搏 前言 在测试中我发现了很多网站开始使用GraphQL技术,并且在测试中发现了其使用过程中存在的问题,那么,到底GraphQL是什么呢?了解了GraphQL后能帮助我们在渗透测试中发现哪些…...
神经网络super(XXX, self).__init__()的含义
学习龙良曲老师的课程,在77节有这样一段代码 import torch from torch import nnclass Lenet5(nn.Module):def __init__(self):super(Lenet5,self).__init__()那么,super(XXX, self).init()的含义是什么? Python中的super(Net, self).init()…...
45.杜芬方程解仿真解曲线(matlab程序)
1.简述 Dufing方程是一种重要的动力系统山,是反映工程物理系统中非线性现象和混沌动力学行为的极其重要的方程式。通过Duffing方程可以探讨铁磁谐振电路中的分岔、拟周期运动、子谐波振荡。而在非线性与混沌系统的研究中,Duffing方程展示了丰富的混沌动力…...
服务器数据恢复-EXT3分区误删除邮件的数据恢复案例
服务器数据恢复环境: 一台服务器有一组由8块盘组建的RAID5阵列,EXT3文件系统。 服务器故障: 由于工作人员的误操作导致文件系统中的邮件丢失。用户需要恢复丢失的邮件数据。 服务器数据恢复过程: 1、将故障服务器中所有磁盘以只…...
C 语言的逗号运算符
逗号运算符 comma operator 逗号运算符最常用在 for 循环的循环头中. 程序示例: #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…...
无人车沿着指定线路自动驾驶与远程控制的实践应用
有了前面颜色识别跟踪的基础之后,我们就可以设定颜色路径,让无人车沿着指定线路做自动驾驶了,视频:PID控制无人车自动驾驶 有了前几章的知识铺垫,就比较简单了,也是属于颜色识别的一种应用,主要…...
C++ 多态性——纯虚函数与抽象类
抽象类是一种特殊的类,它为一个类族提供统一的操作界面。抽象类是为了抽象和设计的目的而建立的。可以说,建立抽象类,就是为了通过它多态地使用其中的成员函数。抽象类处于类层次的上层,一个抽象类自身无法实例化,也就…...
小程序如何使用防抖和节流?
防抖(Debounce)和节流(Throttle)都是用来优化函数执行频率的技术,特别在处理用户输入、滚动等频繁触发的情况下,它们可以有效减少函数的执行次数,从而提升性能和用户体验。但它们的工作方式和应…...
计算机三级网络技术(持续更新)
BGP考点 A S:自治系统 BGP: Border Gateway Protocol(当前使用的版本是 BGP-4)外部网关协议 动态路由协议可以按照工作范围分为IGP以及EGP。IGP工作在同一个AS内,主要用来发现和计算路由,为AS内提供路由信息的交换&…...
Django Rest_Framework(二)
文章目录 1. http请求响应1.1. 请求与响应1.1.1 Request1.1.1.1 常用属性1).data2).query_params3)request._request 基本使用 1.1.2 Response1.1.2.1 构造方式1.1.2.2 response对象的属性1).data2).status_code3&…...
Kotlin~Visitor访问者模式
概念 将数据结构和操作分离,使操作集合可以独立于数据结构变化。 角色介绍 Visitor:抽象访问者,为对象结构每个具体元素类声明一个访问操作。Element:抽象元素,定义一个accept方法ConcreteElement:具体元…...
LVS-DR模式集群构建过程演示
一、工作原理 LVS的工作原理 1.当用户向负载均衡调度器(Director Server)发起请求,调度器将请求发往至内核空间 2.PREROUTING链首先会接收到用户请求,判断目标IP确定是本机IP,将数据包发往INPUT链 3.IPVS是工作在IN…...
UML-A 卷-知识考卷
UML-A 卷-知识考卷 UML有多少种图,请列出每种图的名字: 常用的几种UML图: 类图(Class Diagram):类图是描述类、接口、关联关系和继承关系的图形化表示。它展示了系统中各个类之间的静态结构和关系。时序…...
BpBinder与PPBinder调用过程——Android开发Binder IPC通信技术
在Android系统中,进程间通信(IPC)是一个非常重要的话题。Android系统通过Binder IPC机制实现进程间通信,而Binder IPC通信技术则是Android系统中最为重要的进程间通信技术之一。本文将介绍Binder IPC通信技术的原理,并…...
篇十五:模板方法模式:固定算法的步骤
篇十五:"模板方法模式:固定算法的步骤" 设计模式是软件开发中的重要知识,模板方法模式(Template Method Pattern)是一种行为型设计模式,用于定义一个算法的骨架,将算法中一些步骤的具…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
