*【每日一题 基础题】 [蓝桥杯 2023 省 B] 飞机降落

news/2024/12/25 23:34:02/

题目描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di 个单位时间,即它最早可以于 Ti 时刻开始降落,最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li个单位时间。
一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T,代表测试数据的组数。
对于每组数据,第一行包含一个整数 N。
以下 N 行,每行包含三个整数:Ti,Di 和 Li。
输出格式
对于每组数据,输出 YES 或者 NO,代表是否可以全部安全降落。
样例输入
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 时刻完成降落。
对于第二组数据,无论如何安排,都会有飞机不能及时降落。
对于 30% 的数据,N ≤ 2。
对于 100% 的数据,1 ≤ T ≤ 10,1 ≤ N ≤ 10,0 ≤ Ti , Di , Li ≤ 105。

import java.util.*;  public class Main {  static final int N = 10;  static boolean[] st = new boolean[N];  static int n;  static boolean flag = false;  static int[] t = new int[N];  static int[] d = new int[N];  static int[] l = new int[N];  static void dfs(int u, int last) {  if (flag) return; // If we found one valid sequence, return  if (u == n) { // All planes have landed  flag = true;  return;  }  for (int i = 0; i < n; i++) {  if (!st[i]) { // If the current plane hasn't landed yet  if (t[i] + d[i] >= last) { // Check if it can wait for the last plane to land  st[i] = true; // Mark the plane as landed  if (t[i] > last) { // If this plane arrives after the last one has landed  dfs(u + 1, t[i] + l[i]); // Update last to arrival + landing time  } else { // If this plane arrives before or when the last one is landing  dfs(u + 1, last + l[i]); // Wait for the last plane to land  }  st[i] = false; // Backtrack  } else {  return; // If it can't wait, return  }  }  }  }  public static void main(String[] args) {  Scanner scanner = new Scanner(System.in);  int T = scanner.nextInt();  while (T-- > 0) {  n = scanner.nextInt();  for (int i = 0; i < n; i++) {  t[i] = scanner.nextInt();  d[i] = scanner.nextInt();  l[i] = scanner.nextInt();  }  for (int i = 0; i < N; i++) {  st[i] = false; // Reset the landing status  }  flag = false; // Reset the flag  dfs(0, 0); // Start DFS  if (flag) {  System.out.println("YES");  } else {  System.out.println("NO");  }  }  }  
}
import java.util.*;public class Main {static boolean flag=false;static boolean[] st;static int n;static Map<Integer,int[]> map;//static Scanner cin = new Scanner(System.in);public static void main(String[] args){int t= cin.nextInt();while(t--!=0)solve();}private static void solve() {n= cin.nextInt();flag=false;//标记,如果为true则搜素到答案st=new boolean[n];//初始胡标记数组,标记数组用于查询未安排下降的飞机,如果标记数组全为true,则代表能成功全部安排map=new HashMap<>();for (int i = 0; i < n; i++) {//输入int t= cin.nextInt();int d= cin.nextInt();int l= cin.nextInt();map.put(i,new int[]{t,d,l});}for (int i=0;i<n;i++){//枚举第一架飞机安排st[i]=true;//标记搜索dfs(map.get(i)[0]+map.get(i)[2]);//搜索下一驾飞机应该安排什么,并把时间传入下一个dfs,时间为飞机起飞时间加下降时间st[i]=false;//还原,取消标记}if(flag) System.out.println("YES");if(!flag) System.out.println("NO");}private static void dfs(int time) {boolean ok=true;//下面for循环中,如果没有再安排飞机,则代表已经成功安排所有飞机for (int i=0;i<n;i++){//枚举飞机if(st[i])continue;//如果已经下降了,不用再安排下降ok=false;if(time>map.get(i)[0]+map.get(i)[1])continue;int is=Math.max(time,map.get(i)[0])+map.get(i)[2];//时间取当前时间和飞机起飞时间最大那个,加上飞机下降时间st[i]=true;//标记dfs(is);//搜索下一驾飞机st[i]=false;//还原标记}if(ok)//代表搜素到答案 直接返回flag=true;return;}
}

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

相关文章

HTMLCSSJavaScriptDOM 之间的关系?

一、HTML 中文名&#xff1a;超文本标记语言 英文名&#xff1a;HyperText Markup Language HTML是一种用来结构化Web网页及其内容的标记语言。 HTML 由一系列的元素组成&#xff0c;这些元素可以用来包围不同部分的内容&#xff0c;使其以某种方式呈现或者工作。 图Ⅰ 每…

负载均衡-lvs

负载均衡集群 1、集群是什么&#xff1f; 1 集群&#xff08;cluster&#xff09;技术是一种较新的技术&#xff0c;通过集群技术&#xff0c;可以在付出较低成本的情况下获得在性能、可靠性、灵活性方面的相对较高的收益&#xff0c;其任务调度则是集群系统中的核心技术。 …

前端笔记——大数据量浏览器卡顿优化思路

多任务数据量处理卡顿问题 任务分批次 为避免阻塞&#xff0c;可以将 长时间的单一任务 拆分成多个小任务并分批执行。这样可以在两次任务之间让浏览器有时间处理渲染、用户输入等操作。两种常见方法&#xff1a; setTimeout 方法&#xff1a; 使用 setTimeout 将任务分段&a…

c++类型判断和获取原始类型

std::traits学习 类型判断和退化&#xff08;获取原始类型&#xff09;的原理就是利用模板的特例化。根据调用模板的特例化&#xff0c;在特例化模板中实现判断的逻辑或者退化的逻辑。 一、类型判断 判断整型数据的模板类 #include <iostream> namespace zk {templa…

Linux运维常见命令

vi/vim快捷键使用 1)拷贝当前行 yy ,拷贝当前行向下的5行 5yy&#xff0c;并粘贴&#xff08;输入p&#xff09;。 2)删除当前行 dd ,删除当前行向下的5行5dd 3)在文件中查找某个单词 [命令行下 /关键字&#xff0c;回车查找 ,输入n就是查找下一个 ] 4)设置文件的行号&…

Ubuntu 20.04 卸载和安装 MySQL8.0

卸载 首先&#xff0c;检查一下系统安装的软件包有哪些&#xff0c;使用dpkg -l | grep mysql命令&#xff1a; 为了将MySQL卸载干净&#xff0c;这些文件都需要被删除。 在Ubuntu20.04系统下&#xff0c;卸载干净MySQL8.0以确保下一次安装不会出错&#xff0c;可以按照以下…

微软的AI转型故事

在一次备受瞩目的深度访谈中&#xff0c;微软的CEO萨提亚纳德拉与著名投资人比尔格里和布拉德格斯特纳展开了一场关于微软十年转型与AI未来的深入探讨。这次对话不仅回顾了微软在纳德拉领导下的重大发展轨迹&#xff0c;也为AI时代的战略布局提供了洞见。 纳德拉的职业起点 故…

视频汇聚融合云平台Liveweb一站式解决视频资源管理痛点

随着5G技术的广泛应用&#xff0c;各领域都在通信技术加持下通过海量终端设备收集了大量视频、图像等物联网数据&#xff0c;并通过人工智能、大数据、视频监控等技术方式来让我们的世界更安全、更高效。然而&#xff0c;随着数字化建设和生产经营管理活动的长期开展&#xff0…