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

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

#include <bits/stdc++.h>
using namespace std;
int N, flag, vis[11] = { 0 };
int a[11], b[11], c[11];
void dfs(int num, int cnt, int time)//time表示飞机降落的最早时间
{
    if (cnt == num+1) flag=1;//当所有飞机安排成功,cnt=num+1
    for (int i = 1; i <= num; i++)
    {
        if (!vis[i] && a[i] + b[i] >= time)//到达时间+盘旋时间>=time才能够降落
        {
            //分情况:
            //1:上一架飞机降落完成,下一架飞机还没有到,则time=a[i]+c[i]
            //2:上一架飞机还没降落完成,下一架飞机已经到了,time=time+c[i]
            vis[i] = 1;
            dfs(num, cnt + 1, max(time, a[i]) + c[i]);
            vis[i] = 0;
        }
    }
}
int main()
{
    int K;
    cin >> K;
    while (K--)
    {
        cin >> N;
        for (int i = 1; i <= N; i++)
            cin >> a[i] >> b[i] >> c[i];
        flag = 0;
        vis[N] = { 0 };
        dfs(N, 1, 0);
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}
0 回复 0 转发 4 喜欢 3 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!