思路:
受P1803 凌乱的yyy / 线段覆盖的启发。
对于这道题,我的第一想法不是dfs,而是把它看作区间来看,分别就是【t,t+l】和【t+d,t+d+l】。先按照结束时间排序,先用第一个飞机不延迟降落的时间a[0].end1更新last,然后看其他飞机的最先降落点和最迟降落点,根据降落的时间再来更新last。
初次尝试:20% 我觉得应该是判断条件cmp那里有问题,但是一时间不知道怎么修改。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int n;
struct node{
int t,d,l;
};
node a[100];
struct node1{
int start1,start2,end1,end2;
};
node1 b[100];
bool cmp(node1 aa,node1 bb)
{
if(aa.start1 == bb.start1) return aa.end1<bb.end1;
return aa.end2 < bb.end2;
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i].t>>a[i].d>>a[i].l;
b[i].start1 = a[i].t;
b[i].start2 = a[i].t+ a[i].d;
b[i].end1 = a[i].t + a[i].l;
b[i].end2 = a[i].t + a[i].d + a[i].l;
}
sort(b,b+n,cmp);
// for(int i=0;i<n;i++){
// cout<<b[i].start1<<' '<<b[i].start2<<' '<<b[i].end1<<' '<<b[i].end2<<endl;
// }
bool st = false;
int last = b[0].end1;
for(int i=1;i<n;i++){
if(last < b[i].start1){
last = b[i].end1;
}
else if(last < b[i].start2){
last = b[i].end2;
}
else st = true;
}
if(st == true){
cout<<"NO"<<endl;
}
else cout<<"YES"<<endl;
}
return 0;
}
结果: