第十四届蓝桥杯省赛C++B组D题【飞机降落】题解(AC)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

解题思路

这道题目要求我们判断给定的飞机是否都能在它们的油料耗尽之前降落。为了寻找是否存在合法的降落序列,我们可以使用深度优先搜索(DFS)的方法,尝试所有可能的降落顺序。

首先,我们需要理解题目中的条件。每架飞机在 T i T_i Ti 时刻到达机场上空,剩余油料可以维持 D i D_i Di 个单位时间,降落需要 L i L_i Li 个单位时间。这意味着每架飞机可以在 T i T_i Ti T i + D i T_i+D_i Ti+Di 的时间段内开始降落。

然后,我们可以按照以下步骤来实现 DFS:

  1. 首先,我们初始化一个布尔数组 st[] 来记录每架飞机是否已经降落。
  2. 然后,我们对每架飞机尝试进行降落。这里的 “尝试” 意味着我们需要检查该飞机是否可以在当前的时间内开始降落,即它的开始降落时间是否在 T i T_i Ti T i + D i T_i+D_i Ti+Di 的时间段内。如果可以,我们就让它降落,并把 st[i] 设置为 true
  3. 在一架飞机降落之后,我们递归地对剩下的飞机进行尝试。这一步就是 DFS 的主要部分,我们需要在所有的可能的降落序列中进行搜索。
  4. 如果在某一步我们发现当前的飞机无法在当前的时间内开始降落,我们就返回 false,并在上一层中尝试下一架飞机。
  5. 如果所有的飞机都已经降落,我们就返回 true
  6. 最后,我们对所有飞机进行尝试。如果存在至少一个可以让所有飞机都降落的序列,我们就输出 YES,否则输出 NO

通过以上步骤,我们可以找出是否存在一个合法的降落序列,使得所有的飞机都能在它们的油料耗尽之前降落。

AC_Code

  • C++
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 15;int n;
int a[N], b[N], c[N];
bool st[N];bool dfs(int u, int last, int cnt)
{if (b[u] < last)return false;if (cnt == n)return true;for (int i = 0; i < n; ++ i )if (!st[i]){st[i] = true;if (dfs(i, max(a[u], last) + c[u], cnt + 1))return true;st[i] = false;}return false;
}int main()
{int T;cin >> T;while (T -- ){memset(st, 0, sizeof st);cin >> n;for (int i = 0; i < n; ++ i )cin >> a[i] >> b[i] >> c[i], b[i] += a[i];bool flag = false;for (int i = 0; i < n; ++ i ){st[i] = true;if (dfs(i, 0, 1)){flag = true;break;}st[i] = false;}cout << (flag? "YES": "NO") << endl;}return 0;
}
  • Java
import java.util.*;public class Main {static final int N = 15;static int n;static int[] a = new int[N], b = new int[N], c = new int[N];static boolean[] st = new boolean[N];static boolean dfs(int u, int last, int cnt) {if (b[u] < last) {return false;}if (cnt == n) {return true;}for (int i = 0; i < n; ++i) {if (!st[i]) {st[i] = true;if (dfs(i, Math.max(a[u], last) + c[u], cnt + 1)) {return true;}st[i] = false;}}return false;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int T = scanner.nextInt();while (T-- > 0) {Arrays.fill(st, false);n = scanner.nextInt();for (int i = 0; i < n; ++i) {a[i] = scanner.nextInt();b[i] = scanner.nextInt() + a[i];c[i] = scanner.nextInt();}boolean flag = false;for (int i = 0; i < n; ++i) {st[i] = true;if (dfs(i, 0, 1)) {flag = true;break;}st[i] = false;}System.out.println(flag ? "YES" : "NO");}scanner.close();}
}
  • Python
N = 15
a, b, c = [0]*N, [0]*N, [0]*N
st = [False]*Ndef dfs(u, last, cnt):if b[u] < last:return Falseif cnt == n:return Truefor i in range(n):if not st[i]:st[i] = Trueif dfs(i, max(a[u], last) + c[u], cnt + 1):return Truest[i] = Falsereturn FalseT = int(input().strip())
for _ in range(T):st = [False]*Nn = int(input().strip())for i in range(n):a[i], b[i], c[i] = map(int, input().strip().split())b[i] += a[i]flag = Falsefor i in range(n):st[i] = Trueif dfs(i, 0, 1):flag = Truebreakst[i] = Falseprint("YES" if flag else "NO")

【在线测评】

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/366330.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【OceanBase】OBProxy 无状态的理解

SueWakeup 个人主页&#xff1a;SueWakeup 系列专栏&#xff1a;为祖国的科技进步添砖Java 个性签名&#xff1a;保留赤子之心也许是种幸运吧 本文封面由 凯楠&#x1f4f8;友情提供 目录 前言 OBProxy 无状态的概述 OBProxy 无状态特性带来的优点 1. 高可用 2. 负载均衡…

盛元广通打造智慧校园实验室安全管理系统

盛元广通智慧校园实验室安全管理系统以安全为重点&#xff0c;构建由学校、二级单位、实验室组成的三级联动的实验室安全多级管理体系、多类用户角色&#xff0c;内置教育部标准检查表&#xff0c;支撑实验室相关业务过程的智慧管理。实现通过PC端/手机移动端开展检查工作、手机…

基于贵州非遗推广小程序的设计与实现14362

基于贵州非遗推广小程序的设计与实现 摘 要 本文设计并实现了一个基于贵州非遗推广的小程序&#xff0c;旨在通过小程序平台推广和展示贵州省非物质文化遗产。该小程序提供了非遗项目介绍、相关活动展示、购买非遗产品等功能。 首先&#xff0c;我们收集了贵州省各个非遗项目的…

惠海 H6912 升压恒流芯片IC 支持2.6-40V升12V24V36V48V60V100V 10A 摄影灯 太阳能灯 UV灯 杀菌灯

1.产品描述 H6912是一款外围电路简洁的宽调光比升压调光LED恒流驱动器&#xff0c;可适用于2.6-40V输入 电压范围的LED恒流照明领域。H6912可以实现高精度的恒流效果&#xff0c;输出电流恒流精度≤士3%&#xff0c;电压工作范围为2.6-40V.可以轻松满足锂电池及中低压的应用需…

【Python】Python环境搭建教学#保姆级教学#手把手带你安装——内附Python环境搭建安装包(Python、PyCharm(社区版)安装包)

Python环境搭建 导读一、初识Python1.1 Python的由来1.2 Python的用途1.3 Python的优缺点1.4 Python的前景&#xff08;钱景&#xff09; 二、Python环境搭建2.1 运行环境——Python安装2.2 开发环境——PyCharm安装2.3 项目创建2.4 基本配置2.4.1 主题配置2.4.2 背景图设置2.4…

2024 年江西省研究生数学建模竞赛A题:交通信号灯管理问题分析、实现代码及参考论文

2024 年江西省研究生数学建模竞赛题目交通信号灯管理 1 题目 交通信号灯是指挥车辆通行的重要标志&#xff0c;由红灯、绿灯、 黄灯组成。红灯停、绿灯行&#xff0c;而黄灯则起到警示作用。交通 信号灯分为机动车信号灯、非机动车信号灯、人行横道信号 灯、方向指示灯等。 一…

实体零售连锁企业如何通过物流接口实现数智化转型升级?

在电子商务浪潮的持续冲击下&#xff0c;传统的实体零售行业面临着巨大的挑战。为了在线上线下融合的新零售时代保持竞争力&#xff0c;众多实体零售企业积极寻求数字化转型的突破。 某中国零售连锁百强企业近年来致力于打造自有品牌的线上销售体系&#xff0c;自2021年8月起接…

MySQL:数据类型

数据类型 1. 字符串类型2. 整数类型3. 定点数类型和浮点数类型4. 布尔类型5. 枚举和集合类型6. 日期和时间类型7. Blob类型8. JSON类型 字符串类型、数字类型、日期和时间类型、存放二进制的数据类型、存放地理数据的类型。 1. 字符串类型 字符串类型也可以用来存储邮编&…

Windows server 由于没有远程桌面授权服务器可以提供许可证,远程会话连接已断开。

问题现象&#xff1a; 解决办法 临时远程方式1: 打开 mstsc 时带上 /admin 等参数&#xff0c;如下图所示&#xff1a; 使用“mstsc /admin /v:目标ip”来强制登录服务器&#xff0c;但只能是管理员身份。 远程方式2&#xff1a; 通过VM远程登陆系统后&#xff0c;运行输入R…

【第七节】C/C++排序算法

目录 前言 一、冒泡排序 二、选择排序 三、插入排序 四、希尔排序 五、归并排序 六、快速排序 七、 堆排序 八、计数排序 九、桶排序 十、基数排序 前言 排序算法可以大致分为两大类&#xff1a;比较类排序和非比较类排序。以下是这两大类中一些常见的排序算法示例&…

dledger原理源码分析系列(一)-架构,核心组件和rpc组件

简介 dledger是openmessaging的一个组件&#xff0c; raft算法实现&#xff0c;用于分布式日志&#xff0c;本系列分析dledger如何实现raft概念&#xff0c;以及dledger在rocketmq的应用 本系列使用dledger v0.40 本文分析dledger的架构&#xff0c;核心组件&#xff1b;rpc组…

高等数学在Android开发中的应用:函数极限与算法优化

高等数学在Android开发中的应用:函数极限与算法优化 在Android开发中,高等数学中的许多概念和技术都能够显著提高应用程序的性能和功能。这篇博客将探讨一些具体的数学原理,特别是函数极限在Android中的实际应用。 函数极限的基本概念 函数极限是微积分的基础,广泛应用于…

6.The hardest part about learing hard things(学一件难的事,难在哪里)

I’ve been recording a lot of podcast interviews for my upcoming book, Ultralearning.One of the reurring themes I’ve noticed in our conversations is that how people feel about learning is the overwhelming cause of the results they experience. 我为我的新书…

最新AIGC系统源码-ChatGPT商业版系统源码,自定义ChatGPT指令Promp提示词,AI绘画系统,AI换脸、多模态识图理解文档分析

目录 一、前言 系统文档 二、系统演示 核心AI能力 系统快速体验 三、系统功能模块 3.1 AI全模型支持/插件系统 AI模型提问 文档分析 ​识图理解能力 3.2 GPts应用 3.2.1 GPTs应用 3.2.2 GPTs工作台 3.2.3 自定义创建Promp指令预设应用 3.3 AI专业绘画 3.3.1 文…

基于OpenCV与Keras的停车场车位自动识别系统

本项目旨在利用计算机视觉技术和深度学习算法&#xff0c;实现对停车场车位状态的实时自动识别。通过摄像头监控停车场内部&#xff0c;系统能够高效准确地辨认车位是否被占用&#xff0c;为车主提供实时的空闲车位信息&#xff0c;同时为停车场管理者提供智能化的车位管理工具…

谷歌GenType:1分钟生成AI艺术字母表,小众但好用,完全免费!(附教程)

文章首发于公众号&#xff1a;X小鹿AI副业 大家好&#xff0c;我是程序员X小鹿&#xff0c;前互联网大厂程序员&#xff0c;自由职业2年&#xff0c;也一名 AIGC 爱好者&#xff0c;持续分享更多前沿的「AI 工具」和「AI副业玩法」&#xff0c;欢迎一起交流~ 最近发现一个好玩的…

linux 控制台非常好用的 PS1 设置

直接上代码 IP$(/sbin/ifconfig eth0 | awk /inet / {print $2}) export PS1"\[\e[35m\]^o^\[\e[0m\]$ \[\e[31m\]\t\[\e[0m\] [\[\e[36m\]\w\[\e[0m\]] \[\e[32m\]\u\[\e[0m\]\[\e[33m\]\[\e[0m\]\[\e[34m\]\h(\[\e[31m\]$IP\[\e[m\])\[\e[0m\]\n\[\e[35m\].O.\[\e[0m\]…

云计算【第一阶段(23)】Linux系统安全及应用

一、账号安全控制 1.1、账号安全基本措施 1.1.1、系统账号清理 将非登录用户的shell设为/sbin/nologin锁定长期不使用的账号删除无用的账号 1.1.1.1、实验1 用于匹配以/sbin/nologin结尾的字符串&#xff0c;$ 表示行的末尾。 &#xff08;一般是程序用户改为nologin&…

将exe文件添加到注册表中,实现开机时自动运行

目录 一、前言 二、代码 三、使用步骤 1.编译生成exe文件、 2.以管理员身份运行代码 3.打开注册表&#xff0c;验证结果 一、前言 在Windows操作系统中&#xff0c;将exe文件的路径添加到注册表下&#xff0c;主要用于实现程序的开机自动运行功能。 注册表路径为&#xf…

nlp--最大匹配分词(计算召回率)

最大匹配算法是一种常见的中文分词算法&#xff0c;其核心思想是从左向右取词&#xff0c;以词典中最长的词为优先匹配。这里我将为你展示一个简单的最大匹配分词算法的实现&#xff0c;并结合输入任意句子、显示分词结果以及计算分词召回率。 代码 : # happy coding…