本文主要是介绍蓝桥杯练习-dfs算法飞机降落问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
有 N架飞机准备降落到某个只有一条跑道的机场。
其中第 i架飞机在 Ti时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di 个单位时间,即它最早可以于 Ti时刻开始降落,最晚可以于 Ti+Di 时刻开始降落。
降落过程需要 Li 个单位时间。
一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T ,代表测试数据的组数。
对于每组数据,第一行包含一个整数 N 。
以下 N 行,每行包含三个整数:Ti,Di 和 Li。
输出格式
对于每组数据,输出 YES 或者 NO,代表是否可以全部安全降落。
数据范围
对于 30 30%30 的数据,N ≤ 2 N≤2N≤2 。
对于 100 100%100 的数据,1 ≤ T ≤ 10 1≤T≤101≤T≤10,1 ≤ N
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
#include <vector>
const int N = 10 + 20;
bool st[N];
int n;
struct plant
{int t, d,l; //t到达机场时间,d可以悬停时间,l降落需要时间
}p[N];bool dfs(int count, int time)
{if (count >= n) return true; //count 数量和time可以降落的时间for (int i = 0; i < n; i++){cout << i << endl;if (!st[i]) {st[i] = true; //如果飞机没有降落过,降落这个飞机if (p[i].t + p[i].d < time) //判断到达时间加上停留时间是否可以降落{st[i] = false; cout << i << endl; //不可降落这架飞机return false; //回溯到上一个降落的飞机,本轮跳过这个不可降落飞机}int temp = max(p[i].t, time)+p[i].l; //可以的最早降落时间if (dfs(count + 1, temp))return true; //回溯点cout << "shibai" << endl;st[i] = false;}}return false;}
void slove()
{cin >> n;for (int i = 0; i < n; i++){cin >>p[i].t >> p[i].d >> p[i].l;}if (dfs(0, 0))cout << "YES" << endl;elsecout << "NO" << endl;for (int i = 0; i < n; i++){st[i] = false;}
}
signed main()
{ios::sync_with_stdio;cin.tie(0);cout.tie(0);int n = 1;while (n--)slove();
}
这篇关于蓝桥杯练习-dfs算法飞机降落问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!