当前位置:   article > 正文

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

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

题目描述

N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i T_{i} Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 D i D_{i} Di 个单位时间,即它最早可以于 T i T_{i} Ti 时刻开始降落,最晩可以于 T i + D i T_{i}+D_{i} Ti+Di 时刻开始降落。降落过程需要 L i L_{i} Li 个单位时间。

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

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

输入格式

输入包含多组数据。

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

对于每组数据,第一行包含一个整数 N N N

以下 N N N 行,每行包含三个整数 T i , D i , L i T_{i},D_{i},L_{i} Ti,Di,Li

输出格式

对于每组数据,输出 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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

样例输出 #1

YES
NO
  • 1
  • 2

提示

【样例说明】

对于第一组数据,可以安排第 3 架飞机于 0 时刻开始降落,20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落,30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落,40 时刻完成降落。

对于第二组数据,无论如何安排,都会有飞机不能及时降落。

【评测用例规模与约定】

对于 30 % 30 \% 30% 的数据, N ≤ 2 N \leq 2 N2

对于 100 % 100 \% 100% 的数据, 1 ≤ T ≤ 10 1 \leq T \leq 10 1T10 1 ≤ N ≤ 10 1 \leq N \leq 10 1N10 0 ≤ T i , D i , L i ≤ 1 0 5 0 \leq T_{i},D_{i},L_{i} \leq 10^{5} 0Ti,Di,Li105

蓝桥杯 2023 省赛 B 组 D 题。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define inf 1e18
const int mod=1e9+7;
const int N=2e5+5;
int n,flag;
int t[N],d[N],l[N],vis[N];
void dfs(int p,int cnt){
//	cout<<p<<" "<<cnt<<endl;
	if(cnt==n){
		flag=1;
		return;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0&&p<=t[i]+d[i]){
			vis[i]=1;
			dfs(max(p,t[i])+l[i],cnt+1);
			vis[i]=0;
		}
	}
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>d[i]>>l[i];
	}
	flag=0;
	memset(vis,0,sizeof vis);
	dfs(0,0);
	if(flag) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt=1;
	cin>>tt;
	while(tt--) solve();
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/436225
推荐阅读
相关标签
  

闽ICP备14008679号