题目描述

blablabla

样例

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using PII = pair<int,int>;

constexpr int N = 15;
bool vis[N];
int n;
struct Plane{
    int t,d,l;
};
vector<Plane> planes;


bool dfs(int u,int last){ // u表示已经安排降落的飞机数量，last表示上一架飞机降落完成的时间
    if(u == n) return true;
    for(int i = 0; i < n; i++){
        if(!vis[i] && planes[i].t + planes[i].d >= last){
            vis[i] = true;
            int finish = max(last,planes[i].t) + planes[i].l;
            if(dfs(u + 1,finish)) return true;
            vis[i] = false;
        }

    }
    return false;
}

void solve(){

    cin >> n;
    planes.resize(n);
    memset(vis,false,sizeof(vis));

    for(int i = 0; i < n; i++){
        cin >> planes[i].t >> planes[i].d >> planes[i].l;
    }
    cout << (dfs(0,0) ? "YES\n" : "NO\n");
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    int T = 1;
    cin >> T;
    while(T--){
        solve();
    }

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Plane {
    int arrival;    // 到达时间 Ti
    int fuel;       // 可盘旋时间 Di
    int landing;    // 降落所需时间 Li
    int deadline;   // 最晚开始降落时间 Ti+Di

    Plane(int t, int d, int l) : arrival(t), fuel(d), landing(l) {
        deadline = t + d;
    }
};

bool canAllPlanesLand(vector<Plane>& planes) {
    // 按照最晚开始降落时间（deadline）排序
    sort(planes.begin(), planes.end(), [](const Plane& a, const Plane& b) {
        return a.deadline < b.deadline;
    });

    int currentTime = 0;

    for (const Plane& plane : planes) {
        // 如果当前时间小于飞机到达时间，更新当前时间
        currentTime = max(currentTime, plane.arrival);

        // 检查飞机是否能在最后期限前开始降落
        if (currentTime > plane.deadline) {
            return false;
        }

        // 飞机开始降落，更新当前时间
        currentTime += plane.landing;
    }

    return true;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<Plane> planes;
        for (int i = 0; i < N; i++) {
            int t, d, l;
            cin >> t >> d >> l;
            planes.emplace_back(t, d, l);
        }

        if (canAllPlanesLand(planes)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}