返回题解分享
讨论 / 题解分享/ 帖子详情

飞机降落(编程题) - 题解

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

struct Airplane {
    int T;
    int D;
    int L;
};

bool backtrack (vector<Airplane>& planes, vector<bool>& used,
 int index, int currentTime) {
    if (index == planes.size()) {
        return true;
    }

    for (int i = 0; i < planes.size(); i++) {
        if (!used[i]) {
            int earliest = max(currentTime, planes[i].T);
            int latest = planes[i].T + planes[i].D;
            if (earliest <= latest) {
                used[i] = true;
                if (backtrack(planes, used, index + 1, earliest + planes[i].L)) {
                    return true;
                }
            }
            used[i] = false;
        }
    }
    return false;
 }

bool canAllLand (vector<Airplane>& planes) {
    int n = planes.size();
    vector<bool> used(n, false);
    return backtrack(planes, used, 0, 0);
}

int main() {
    int t, N;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> N;
        vector<Airplane> planes(N);
        for (int j = 0; j < N; j++) {
            cin >> planes[j].T >> planes[j].D >> planes[j].L;
        }

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

    return 0;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!