[蓝桥杯 2023 省 B] 飞机降落（不会dfs的看过来）

2025-05-03 10:00:49 0 阅读

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

题目描述

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

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

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

输入格式

输入包含多组数据。

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

对于每组数据，第一行包含一个整数 $N$ 。

以下 $N$ 行，每行包含三个整数 $T_{i},D_{i},L_{i}$ 。

输出格式

对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。

输入输出样例 #1

输入 #1

输出 #1

YES
NO

说明/提示

【样例说明】

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

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

【评测用例规模与约定】

对于 $30 %$ 的数据， $N \leq 2$ 。

对于 $100 %$ 的数据， $1 \leq T \leq 10$ ， $1 \leq N \leq 10$ ， $T_{i},D_{i},L_{i} leq 10^{5}$ 。

蓝桥杯 2023 省赛 B 组 D 题。

分析

这个题数据量不大，直接暴搜，把每种飞机降落的顺序都试一遍，有成功的就YES，都不行就NO

尝试每一种顺序的时候，如果当前时间time已经超过该飞机的最晚降落时间D[i]了，那么它就降落不了了，当前顺序就不行，直接跳出来试下一种方案；

如果当前时间还不到飞机的最早到达时间T[[i]，那就等到飞机到达的时间，所以在当前飞机降落前，time=max(T[i], time)，即让时间同步到飞机可以开始降落的时间

如果飞机可以顺利降落（当前时间time不晚于飞机的最晚降落时间D[i]），那就将当前时间加上降落所需时间L[i]，再去尝让下一架飞机降落

都降落完了，说明当前方案就可以，直接跳出来输出YES就行了

如果遍历完了所有的降落顺序，都不能让所有飞机降落，那就说明是NO

至于如何得到所有的降落顺序，可以用dfs，不过本蒟蒻选择用枚举全排列（~~其实是不会dfs~~ ）next_permutation(start,end)函数

next_permutation()

函数作用

字典序生成
next_permutation()会将当前序列按字典序调整为下一个更大的排列。例如，序列 {1,2,3} 的下一个排列是 {1,3,2}。若当前序列已是字典序最大的排列（如 {3,2,1}），则函数返回 false 并将序列重置为最小排列。

基本用法

函数原型与参数

#include   // 必须包含的头文件

template <class BidirectionalIterator>
bool next_permutation(
    BidirectionalIterator first, 
    BidirectionalIterator last
    //, Compare comp  // 可选：自定义比较函数
);

参数：

first / last：定义序列范围的迭代器（左闭右开区间 [first, last)）。
comp（可选）：自定义比较函数，用于非默认排序规则（如降序）。

使用示例

#include 
#include 
#include 

int main() {
    std::vector<int> nums = {1, 2, 3};
    do {
        for (int num : nums) 
            std::cout << num << " ";
        std::cout << "
";
    } while (std::next_permutation(nums.begin(), nums.end()));
    return 0;
}

输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

所以我们可以利用next_permutation()函数生成飞机降落的所有顺序（飞机按0，…，n-1编号，当然从1到n也行），然后依次尝试即可

代码

#include
#include   
using namespace std;
int t, n;
int num[20];//存储飞机降落的顺序
int T[20], d[20], l[20];
int flag = 0;
int main() {
    cin >> t;
    for (int i = 0; i < t; i++) {
        flag = 0;
        cin >> n;
        for (int j = 0; j < n; j++)
            num[j] = j;
        for (int j = 0; j < n; j++) {
            cin >> T[j] >> d[j] >> l[j];
            d[j] += T[j];//存储最晚降落时间
        }
        do {
            int time = 0;
            int j = 0;
            for (j = 0; j < n; j++) {//当前要降落的飞机是num[j]
                time = max(time, T[num[j]]);//当前飞机降落时间
                if (time > d[num[j]]) {//超出当前飞机降落时间
                    time = 0;
                    break;//其他飞机不用试了，当前方案不行
                }
                else {//当前飞机可以降落
                    time += l[num[j]];
                }
            }
            if (j == n) {//n架飞机都可以降落
                flag = 1;
                break;//当前降落方案可以
            }
        } while (next_permutation(num, num + n));//所有的降落方案
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}