网站 如何添加备案号,网站app微信三合一,网站建设本地还是外地,三亚做网站哪家好蓝桥杯飞机降落dfs深度解析 蓝桥杯14届省赛[飞机降落]题目描述输入格式输出格式样例输入样例输出提示code完整代码#xff1a; 蓝桥杯14届省赛[飞机降落]
题目描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空#xff0c;到达时它的… 蓝桥杯飞机降落dfs深度解析 蓝桥杯14届省赛[飞机降落]题目描述输入格式输出格式样例输入样例输出提示code完整代码 蓝桥杯14届省赛[飞机降落]
题目描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空到达时它的剩余油料还可以继续盘旋 Di 个单位时间即它最早
可以于 Ti 时刻开始降落最晚可以于 Ti Di 时刻开始降落。降落过程需要 Li个单位时间。
一架飞机降落完毕时另一架飞机可以立即在同一时刻开始降落但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T代表测试数据的组数。
对于每组数据第一行包含一个整数 N。
以下 N 行每行包含三个整数TiDi 和 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 ≤ 101 ≤ N ≤ 100 ≤ Ti , Di , Li ≤ 105。 ## 解题思路
1.看数据范围 共有 T 组数据T 最大为 10 N最大为 10 所以可以先想暴力解法。
2.暴力解法做法 对于 N 架飞机 枚举出他们的全排列然后看其中一种能否安全的降落所有飞机。
我觉得这个题的难点主要有两点
我看到这个题的第一时间会想到排序因为我没有看到数据范围所以想到的是贪心排序后能否按照排序后的结果去安全的降落飞机。也就是说第一时间可能想不到暴力搜索。可能是题刷少了在暴力搜索的过程中判断飞机是否能够安全停靠的条件很难想出来。 code
1.写出深度优先搜索模板 (顺便回顾如何全排列)
void dfs(int step) {if(step n ) {结束条件return ;}for(int i 0; i n; i ) {if(!book[i]) {book[i] true;dfs(step 1);book[i] false;}}
}2.复习全排列写法
#include iostream
using namespace std;const int N 20;
int n, book[N], a[N];void dfs(int step) {if(step n) {for(int i 0; i n; i ) couta[i] ;coutendl;return ;}for(int i 0; i n; i ) {if(!book[i]) {book[i] 1;a[step] i 1;dfs(step 1);a[step] 0;book[i] 0;}}
}int main() {cinn;dfs(0);return 0;
}3.写出本题飞机能安全停靠的条件判断
由于飞机到达时间 T , 可以盘旋时间 D降落需要时间 L
可以知道飞机只要在 T ~ T D 这段时间降落就可以停下当然安全降落会消耗时间 L
那么也就是说停靠上一架飞机时间 time 满足 T time T D, 飞机就可以安全降落 然后降落会耗费时间 L 也就是停靠下一次飞机的时候。当前时间 time更新为 time time L
你以为这样就万事大吉了吗错
我们还没有考虑到 其实当 time T 的时候也就是说上一架飞机安全停靠后过了一段时间当前这架飞机才到机场也就是说当
time T 的时候实际上我们当前飞机都不用耗费燃料 D 盘旋也就是说time T 不影响我们能否安全降落也就是说可以去除条件 T time, 也就是说 当 time T D 的时候就可以安全降落。
你以为这样又往事大吉了吗错
当时间更新的时候我们需要考虑到当飞机停靠时间 time 在时间 T之前我们真实去停靠完成这架飞机的时间应该是 T 而不是 time L,所以更新时间可以写为 time max(time, T) L;
完整代码
#include iostream
using namespace std;const int N 20;
int n, t, book[N], T[N], D[N], L[N];
bool result;void dfs(int step, int time) {if(step n) {result true;return;} for(int i 0; i n; i ) {if(!book[i] time T[i] D[i]) {book[i] 1;dfs(step 1, max(time, T[i]) L[i]);book[i] 0;}}return;
}int main() {cint;while(t --) {cinn;for(int i 0; i n; i ) cinT[i]D[i]L[i];result false;dfs(0, 0);if(result) coutYESendl;else coutNOendl;}return 0;
}
