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

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

题目描述

$N$ 架飞机准备降落到某个只有一条跑道的机场。其中第 $i$ 架飞机在 $T_i$ 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 $D_i$ 个单位时间，即它最早可以于 $T_i$ 时刻开始降落，最晩可以于 $T_i+D_i$ 时刻开始降落。降落过程需要 $L_i$ 个单位时间。

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

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

输入格式

输入包含多组数据。

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

对于每组数据，第一行包含一个整数 $N$。

以下 $N$ 行，每行包含三个整数 $T_i,D_i,L_i$。

输出格式

对于每组数据，输出 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\%$ 的数据，$N\le 2$。

对于 $100\%$ 的数据，$1\le T\le 10$，$1\le N\le 10$，$0\le T_i,D_i,L_i\le 10^5$。

蓝桥杯 2023 省赛 B 组 D 题。

分析

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

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

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

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

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

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

至于如何得到所有的降落顺序，可以用dfs，不过本蒟蒻选择用枚举全排列（其实是不会dfs ）next_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（可选）：自定义比较函数，用于非默认排序规则（如降序）。

2. 使用示例

#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