当前位置: 首页 > 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;将算法中一些步骤的具…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...