编写题解 3151: 蓝桥杯2023年第十四届省赛真题-飞机降落（注释清晰，简单易懂）

解题思路:

注意事项:

参考代码:

#include <stdio.h>

#include <stdlib.h>

//定义结构体出错每架飞机的三个元素

typedef struct {

  int t;

  int d;

  int l;

} Plane;

//定义全局变量便于各个位置使用使用

int N;

Plane planes[10];

int visited[10];

int flag;

// 深度优先搜索

// current_time: 当前跑道被占用到什么时间（即上一架飞机降落结束的时间）

// count: 已经成功安排的飞机数量

void dfs(int current_time,int count) {

  //已经找到一种方案安排好所有飞机

  if(flag || count == N) {

    flag = 1;

    return;

  }

  // 尝试每一架还没安排的飞机

  for(int i=0;i<N;i++) {

    if(!visited[i]) {

      // 计算这架飞机最早能开始降落的时间

      // 不能早于它到达的时间 (planes[i].t)

      // 也不能早于跑道空闲的时间 (current_time)

      int start_time = current_time;

      if(planes[i].t > start_time) {

        start_time = planes[i].t;

      }

      // 计算最晚必须开始降落的时间

      int last_time = planes[i].t + planes[i].d;

      // 剪枝：如果最早开始时间都超过了最晚允许时间，这架飞机就不能选

      if(start_time <= last_time) {

        //合适则标记为已选

        visited[i] = 1;

        // 递归：新的当前时间 = 开始时间 + 降落耗时

        dfs(start_time + planes[i].l,count + 1);

        // 回溯：如果这条路走不通，撤销标记，尝试下一架

        visited[i] = 0;

        // 如果已经找到了解，就不需要继续尝试了

        if(flag) {

          return;

        }

      }

    }

  }

}

int main(int argc, char *argv[])

{

  int T;

  scanf("%d",&T);

  for(int i=0;i<T;i++) {

    scanf("%d",&N);

    //初始化

    for(int i=0;i<N;i++) {

      scanf("%d %d %d",&planes[i].t,&planes[i].d,&planes[i].l);

      visited[i] = 0;

    }

    flag = 0;

    // 从时间 0 开始，已安排 0 架飞机

    dfs(0,0);

    if(flag)

      printf("YES\n");

    else

      printf("NO\n");

  }

  return 0;

}