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

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

#include <bits/stdc++.h>
using namespace std;
int T[15], D[15], L[15], lable[15], num[15];
int n;
bool flag = false;

void dfs(int cur)
{
    if (flag == true)
        return; // 只要找到了至少1个结果就直接返回

    if (cur == n + 1)
    {
        bool valide = true;
        int tm = T[num[1]];
        for (int i = 1; i <= n; i++)
        {   //当前时刻tm小于等于飞机到的时间+其盘旋的时间,则能正常降落,否则将会有冲突,上一辆飞机降落完,下一辆飞机已经没油了,tm时刻更新时,应该按照飞机序列实际降落的时间更新
            if (tm <= (T[num[i]] + D[num[i]]))
            {
                tm =max(tm + L[num[i]], T[num[i]] + L[num[i]])
            }
            else
            {
                valide = false;
                break;
            }
        }
        if (valide)
        {
            flag = true;
        }

        return;
    }

    for (int i = 1; i <= n; i++)
    {

        // 开始深搜
        if (lable[i] == 0) // 如果当前位置没有被标记
        {
            lable[i] = 1;
            num[cur] = i; // 全排列数值
            dfs(cur + 1);
            lable[i] = 0;
        }
    }
}

void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d %d", &T[i], &D[i], &L[i]);
    }
    flag = false;
    dfs(1);
    if (flag)
        printf("YES\n");
    else
        printf("NO\n");
    return;
}
int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
        solve();
    return 0;
}
0 回复 0 转发 0 喜欢 0 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!