2023年第十四届蓝桥杯省赛C++B组【第四题：飞机降落】_蓝桥杯飞机降落问题

 这道题在AcWing上面似乎数据有做加强，但是根据本蒟蒻的获奖情况来看，蓝桥杯全排列应该可以过。

全排列复杂度最高约为：10*10!，三千万左右。

可以得出的结论是，全排列能做的题目，深搜也一定能做。所以最好舍弃这种最笨的暴力，选择深搜。

TLE代码（全排列）

#include <bits/stdc++.h>
using namespace std;
const int N=11;
 
int n,t[N],d[N],l[N],T,a[N];
bitset<N>vis;
inline int read(){
    int x=0;char ch=getchar();
    while(ch>'9' or ch<'0')ch=getchar();
    while(ch>='0' and ch<='9')x=(x<<3)+(x<<1)+(ch xor 48),ch=getchar();
    return x;
}
inline void work(){
    n=read();
    for(int i=1;i<=n;++i){
        t[i]=read();
        d[i]=read();
        l[i]=read();
        a[i]=n-i+1;
    }
 
    bool can=false;
    do{
        vis.reset();
        int now=1,nowtime=0;
 
        while(now<=n){
            //如果有一架飞机已经不能降落，则直接下一个排列
            for(int i=1;i<=n;++i)
                if(!vis[i] and nowtime>t[i]+d[i])goto nxt;
            //降落飞机
            for(int i=1;i<=n;++i)
                if(a[i]==now){
                    now++;
                    if(nowtime<t[i])nowtime=t[i];
                    nowtime+=l[i];
                    vis[i]=true;
                    break;
                }
        }
        can=true;
        break;
        nxt:{};
    }while(prev_permutation(a+1,a+n+1));
 
    if(can)printf("YES\n");
    else printf("NO\n");
}
 
int main(){
    T=read();
    while(T--)work();
    return 0;
}

用prev_permutation是因为感觉答案可能分布在后面的排列，所以用prev试试，显然我这是在做梦。

回归正题，首先画出解空间树。

可以发现每一次都可以任选一架飞机去降落，当然前提是这个飞机没有降落过，即

void dfs(int now){
    for(int i=1;i<=n;++i)
        if(!vis[i]){
            vis[i]=true;
            dfs(now);
        }
}

根据要题目要求，给递归加入需要携带的参数。

void dfs(int cnt,int nowtime){
    if(can)return;//如果已经有一个排列完成任务，全部结束
    if(cnt==n){//所有飞机都成功降落
        can=true;
        return;
    }
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            if(nowtime>t[i]+d[i])return;//这个飞机不能被降落,结束这一个分支(比全排列更优的地方)
            vis[i]=true;
            if(nowtime<t[i])dfs(cnt+1,t[i]+l[i]);//可能存在前一架飞机降落了,但是后一架飞机还没到的情况,要等到t[i]再继续
            else dfs(cnt+1,nowtime+l[i]);
            vis[i]=false;//递归结束,往前回溯
        }
    }
}

AC代码（深度优先搜索）

#include <bits/stdc++.h>
using namespace std;
const int N=11;
 
int n,T,t[N],d[N],l[N];
bitset<N>vis;
bool can;
inline int read(){
    int x=0;char ch=getchar();
    while(ch>'9' or ch<'0')ch=getchar();
    while(ch>='0' and ch<='9')x=(x<<3)+(x<<1)+(ch xor 48),ch=getchar();
    return x;
}
void dfs(int cnt,int nowtime){
    if(can)return;
    if(cnt==n){
        can=true;
        return;
    }
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            if(nowtime>t[i]+d[i])return;
            vis[i]=true;
            if(nowtime<t[i])dfs(cnt+1,t[i]+l[i]);
            else dfs(cnt+1,nowtime+l[i]);
            vis[i]=false;
        }
    }
}
inline void work(){
    n=read();
    for(int i=1;i<=n;++i)
        t[i]=read(),d[i]=read(),l[i]=read();
 
    vis.reset();
    can=false;
    dfs(0,0);
    if(can)printf("YES\n");
    else printf("NO\n");
}
 
int main(){
    T=read();
    while(T--)work();
    return 0;
}