[蓝桥杯 2023 省 B] 飞机降落(不会dfs的看过来)

ops/2025/3/20 13:51:00/

[蓝桥杯 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/ops/167294.html

相关文章

【云原生之kubernetes实战】在k8s环境中高效部署minio对象存储(详细教程)

【云原生之kubernetes实战】在k8s环境中高效部署minio对象存储(详细教程) 前言一、minio介绍1.1 MinIO简介1.2 主要特点1.3 主要使用场景二、相关知识介绍2.1 本次实践存储介绍2.2 k8s存储介绍三、本次实践介绍3.1 本次实践简介3.2 本次环境规划3.3 部署前需准备工作四、检查…

django小案例-2

1.项目创建 1.1 创建django项目 创建项目的命令如下&#xff1a; django-admin startproject test1 创建成功后的文件夹如下图&#xff1a; __init__.py: 说明test1是一个python包。 settings.py: 项目的配置文件。 urls.py: 进行url路由的配置。 wsgi.py: web服务器和D…

动作捕捉手套如何让虚拟现实人机交互 “触手可及”?

在虚拟与现实逐渐交融的当下&#xff0c;动作捕捉技术正以前所未有的速度革新着多个领域。 动作捕捉技术&#xff0c;简称“动捕”&#xff0c;已经从早期的影视特效制作&#xff0c;逐步拓展到游戏开发、虚拟现实、机器人控制等多个领域。 而mHandPrO数据手套作为这一领域的…

虚幻基础:动作系统3

文章目录 self-Tag&#xff1a;可以直接在游戏运行时通过标签区分不同Actorsolid隔离&#xff1a;模块化低耦合&#xff1a;将功能拆分成多个模块&#xff0c;修改单一模块时无需修改其他模块 动作优先级&#xff1a;当前动作能否打断上一动作函数不能使用timelineset timer by…

蓝桥杯备考:奶牛晒衣服

这道题第一眼想用贪心做&#xff0c;1 2 3 我们可以让最多的3用烘干机1秒就能完成&#xff0c;那么是不是我们每次都给湿度最大的衣服用烘干机呢&#xff1f;我们试试哈&#xff0c;比如[5,8]&#xff0c;每秒晒干1我们给8衣服一直用烘干机是需要4秒的&#xff0c;4秒后8这个…

A l密码学(Deepseek)

我&#xff1a;qwertyuiopasdfghjklzxcvbnm deepseek:深度思考中&#xff0e; Okay, lets see. The user input is "qwertyuiopasdfghjklzxcvbnm". At first glance, it looks like a jumbled sequence of letters with some spaces or maybe other characters in …

Matlab 汽车二自由度转弯模型

1、内容简介 Matlab 187-汽车二自由度转弯模型 可以交流、咨询、答疑 2、内容说明 略 摘 要 本文前一部分提出了侧偏角和横摆角速度作为参数。描述了车辆运动的运动状态&#xff0c;其中文中使用的参考模型是二自由度汽车模型。汽车速度被认为是建立基于H.B.Pacejka的轮胎模…

在 Visual Studio Code 中高效使用 Pylance:配置、技巧与插件对比

在 Visual Studio Code 中高效使用 Pylance&#xff1a;配置、技巧与插件对比 目录 什么是 Pylance&#xff1f;安装与启用核心配置详解高效使用技巧Pylance vs Jedi&#xff1a;深度对比常见问题与优化总结 1. 什么是 Pylance&#xff1f; ‌Pylance‌ 是微软为 VSCode Pyth…