[蓝桥杯 2023 省 B] 飞机降落

news/2025/3/18 16:00:09/

[蓝桥杯 2023 省 B] 飞机降落

题目描述

N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i T_{i} Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 D i D_{i} Di 个单位时间,即它最早可以于 T i T_{i} Ti 时刻开始降落,最晩可以于 T i + D i T_{i}+D_{i} Ti+Di 时刻开始降落。降落过程需要 L i L_{i} Li 个单位时间。

一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。

请你判断 N N N 架飞机是否可以全部安全降落。

输入格式

输入包含多组数据。

第一行包含一个整数 T T T,代表测试数据的组数。

对于每组数据,第一行包含一个整数 N N N

以下 N N N 行,每行包含三个整数 T i , D i , L i T_{i},D_{i},L_{i} Ti,Di,Li

输出格式

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

输入输出样例 #1

输入 #1

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

输出 #1

YES
NO

说明/提示

【样例说明】

对于第一组数据,可以安排第 3 架飞机于 0 时刻开始降落,20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落,30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落,40 时刻完成降落。

对于第二组数据,无论如何安排,都会有飞机不能及时降落。

【评测用例规模与约定】

对于 30 % 30 \% 30% 的数据, N ≤ 2 N \leq 2 N2

对于 100 % 100 \% 100% 的数据, 1 ≤ T ≤ 10 1 \leq T \leq 10 1T10 1 ≤ N ≤ 10 1 \leq N \leq 10 1N10 0 ≤ T i , D i , L i ≤ 1 0 5 0 \leq T_{i},D_{i},L_{i} \leq 10^{5} 0Ti,Di,Li105

蓝桥杯 2023 省赛 B 组 D 题。

分析

这个题数据量不大,直接暴搜,把每种飞机降落的顺序都试一遍,有成功的就YES,都不行就NO

尝试每一种顺序的时候,如果当前时间time已经超过该飞机的最晚降落时间D[i]了,那么它就降落不了了,当前顺序就不行,直接跳出来试下一种方案;

如果当前时间还不到飞机的最早到达时间T[[i],那就等到飞机到达的时间,所以在当前飞机降落前,time=max(T[i], time),即让时间同步到飞机可以开始降落的时间

如果飞机可以顺利降落(当前时间time不晚于飞机的最晚降落时间D[i]),那就将当前时间加上降落所需时间L[i],再去尝让下一架飞机降落

都降落完了,说明当前方案就可以,直接跳出来输出YES就行了

如果遍历完了所有的降落顺序,都不能让所有飞机降落,那就说明是NO

至于如何得到所有的降落顺序,可以用dfs,不过本蒟蒻选择用枚举全排列(其实是不会dfsnext_permutation(start,end)函数

next_permutation()

函数作用

  • ​字典序生成
    next_permutation() 会将当前序列按字典序调整为下一个更大的排列。例如,序列 {1,2,3} 的下一个排列是 {1,3,2}。若当前序列已是字典序最大的排列(如 {3,2,1}),则函数返回 false 并将序列重置为最小排列。

基本用法

  1. 函数原型与参数
#include <algorithm>  // 必须包含的头文件template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last//, Compare comp  // 可选:自定义比较函数
);

​参数:

  • first / last:定义序列范围的迭代器(左闭右开区间 [first, last))。
  • comp(可选):自定义比较函数,用于非默认排序规则(如降序)。
  1. 使用示例
#include <iostream>
#include <algorithm>
#include <vector>int main() {std::vector<int> nums = {1, 2, 3};do {for (int num : nums) std::cout << num << " ";std::cout << "\n";} while (std::next_permutation(nums.begin(), nums.end()));return 0;
}

输出:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

所以我们可以利用next_permutation()函数生成飞机降落的所有顺序(飞机按0,…,n-1编号,当然从1到n也行),然后依次尝试即可

代码

#include<iostream>
#include <algorithm>  
using namespace std;
int t, n;
int num[20];//存储飞机降落的顺序
int T[20], d[20], l[20];
int flag = 0;
int main() {cin >> t;for (int i = 0; i < t; i++) {flag = 0;cin >> n;for (int j = 0; j < n; j++)num[j] = j;for (int j = 0; j < n; j++) {cin >> T[j] >> d[j] >> l[j];d[j] += T[j];//存储最晚降落时间}do {int time = 0;int j = 0;for (j = 0; j < n; j++) {//当前要降落的飞机是num[j]time = max(time, T[num[j]]);//当前飞机降落时间if (time > d[num[j]]) {//超出当前飞机降落时间time = 0;break;//其他飞机不用试了,当前方案不行}else {//当前飞机可以降落time += l[num[j]];}}if (j == n) {//n架飞机都可以降落flag = 1;break;//当前降落方案可以}} while (next_permutation(num, num + n));//所有的降落方案if (flag)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

在这里插入图片描述
顺利AC


http://www.ppmy.cn/news/1580102.html

相关文章

vue3怎么和大模型交互?

引言 平时我们都是用的在线的AI工具&#xff0c;直接输入问题&#xff0c;然后AI回答我们&#xff0c;那么怎么把AI接入项目中呢&#xff1f; 这个问题问得好。 方案一&#xff1a;引入第三方已封装好的UI库方案二&#xff1a;自己写 对于方案一&#xff0c;市面上已有一些…

矩阵的逆的实际意义及牛顿法中的作用

矩阵的逆的实际意义及牛顿法中的作用 目录 矩阵的逆的实际意义及牛顿法中的作用**一、矩阵逆的实际意义****二、牛顿法中矩阵逆的作用****三、实际应用中的挑战与改进**总结一、矩阵逆的实际意义 线性方程组求解 若 A x = b \mathbf{A}\mathbf{x} = \mathbf{b} Ax=<

《Python实战进阶》No22 Python自动化办公实战:Excel/Word/PDF文件处理全攻略

No22 Python自动化办公实战&#xff1a;Excel/Word/PDF文件处理全攻略 摘要 本文将带你掌握Python在办公自动化领域的三大核心场景&#xff1a;Excel数据处理、Word文档生成与PDF文件操作。通过实战案例&#xff0c;你将学会如何用openpyxl、pandas、python-docx、PyPDF2等工具…

Tauri + Vite + SvelteKit + TailwindCSS + DaisyUI 跨平台开发详细配置指南(Windows)

Tauri Vite SvelteKit TailwindCSS DaisyUI 跨平台开发详细配置指南&#xff08;Windows&#xff09; 本文为博主原创文章&#xff0c;遵循 CC 4.0 BY-SA 版权协议。转载请注明出处及本声明 原文链接&#xff1a;[你的文章链接] &#x1f6e0;️ 环境准备 1. 安装核心工具…

发现一个GoVCL的问题

之前用govcl写了一个服务端的界面程序&#xff0c;用来控制服务的开启和关闭。 由于这个服务程序运行的时间比较长&#xff0c;经常是挂着在服务器上24小时不间断运行。 后来经过调试发现&#xff0c;govcl的界面按钮控件&#xff0c;在程序长时间运行后&#xff0c;会出现无法…

失败的面试经历(ʘ̥∧ʘ̥)

一.面向对象的三大特性 1.封装&#xff1a;将对象内部的属性私有化&#xff0c;外部对象不能够直接访问&#xff0c;但是可以提供一些可以使外部对象操作内部属性的方法。 2.继承&#xff1a;类与类之间会有一些相似之处&#xff0c;但也会有一些异处&#xff0c;使得他们与众…

不用 Tomcat?SpringBoot 项目用啥代替?

在SpringBoot框架中&#xff0c;我们使用最多的是Tomcat&#xff0c;这是SpringBoot默认的容器技术&#xff0c;而且是内嵌式的Tomcat。 同时&#xff0c;SpringBoot也支持Undertow容器&#xff0c;我们可以很方便的用Undertow替换Tomcat&#xff0c;而Undertow的性能和内存使…

简述下npm,cnpm,yarn和pnpm的区别,以及跟在后面的-g,--save, --save-dev代表着什么

文章目录 前言一、npm&#xff0c;cnpm&#xff0c;yarn和pnpm的基本介绍和特点1.npm (Node Package Manager)2. Yarn3. cnpm (China npm)4. pnpm 二、简述npm和pnpm 的存储方式和依赖数1.存储方式2.依赖树 三、两者依赖树的差异导致结果的对比四、简单说说-g&#xff0c;--sav…