蓝桥杯2023年第十四届省赛真题-飞机降落 - C语言网 (dotcpp.com)
题目描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di 个单位时间,即它最早
可以于 Ti 时刻开始降落,最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li个单位时间。
一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
分析
由于贪心没法证明,只能通过部分数据,可以使用递归搜索每一种情况,使用类似“全排列”代码,从第0架飞机,第0时间开始搜索,记录下第几架飞机使用过,如果u == n说明所有的飞机都已经安排好。
注:last记录上一架飞机落地的时间
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node
{
int t, d, l;
}a[N];
int flag, n, k;
bool st[N];
bool dfs(int u, int last)
{
if(u == n)
{
return true;
}
for(int i = 1; i <= n; i ++)
{
int d = a[i].d, t = a[i].t, l = a[i].l;
if(!st[i] && d + t >= last)
{
st[i] = true;
if(dfs(u + 1, max(last, t) + l))return true;
st[i] = false;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> k;
while(k --)
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i].t >> a[i].d >> a[i].l;
}
memset(st, 0, sizeof st);
if(dfs(0, 0))cout << "YES" << '\n';
else cout << "NO" << '\n';
}
return 0;
}