蓝桥杯——飞机降落

题目描述

N架飞机准备降落到某个只有一条跑道的机场。其中第i架飞机在Ti时刻到达机场上空，到达时它的剩余油料还可以继续盘旋Di个单位时间，即它最早可以于Ti时刻开始降落，最晚可以于Ti+Di时刻开始降落。降落过程需要Li个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断N架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数T，代表测试数据的组数。
对于每组数据，第一行包含一个整数N。
以下N行，每行包含三个整数：Ti，Di和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时刻完成降落。
对于第二组数据，无论如何安排，都会有飞机不能及时降落。
评测用例规模与约定
N≤2。对于30％的数据，N≤2。
对于100％的数据，1≤T≤10,1≤N≤10;0≤Ti,Di,Li≤10^5。

解题思路

首先确定本题使用dfs,到达时刻，盘旋时间，下降过程分别用3个数组保存，每组数据成功与否用flag标志记录，每次挑选一架飞机尝试降落，满足条件后成功下降飞机数cnt+1，已用时间tt改变并继续下一个dfs,最终cnt==m(总飞机数)即该方案成功。

完整代码

#include <iostream>
using namespace std;
int t,n,f[20],d[20],l[20];
int book[20],flag=0,total=0,sum=0;

 int max(int a,int b){
  if(a>=b) return a;
  else return b;
}

 void dfs(int tt,int cnt,int m){
  if(cnt==m){//m为总飞机数
    flag=1;
    return ;
  }

  for(int i=1;i<=m;i++){
    if(book[i]==0&&f[i]+d[i]>=tt){
      book[i]=1;
     // tt=max(f[i],tt)+l[i];
     //应该用临时变量保存已用时间，不能改变当前这轮的tt值 
     int tmp=max(f[i],tt)+l[i];
      dfs(tmp,cnt+1,m);
      book[i]=0;
    }
  }
  return ;
}

int main()
{
  // 请在此输入您的代码
  cin>>t;//测试组数
  while(t--){
    cin>>n;//飞机数
    for(int i=1;i<=n;i++){
      cin>>f[i]>>d[i]>>l[i];//输入来，盘旋，下降过程时间
      
    }
    flag=0;
    //每组数据flag置0 
    dfs(0,0,n);
    //初始的已用时间和已降落飞机数置0 
    if(flag==1) cout<<"YES";
    else cout<<"NO";
    printf("\n");
  }
  return 0;
}