蓝桥杯2023年第十四届省赛真题-飞机降落（暴力枚举） 基于全排列函数next_permutation

解题思路:

注意事项:
有题目数据范围飞机数量 n<=10，可知本问题可对所有飞机的下落顺序进行全排（最大循环次数10！*10约为3e7,可过所有样例），得到得所以方案中有一种满足即为YES。即当得到一种可行方案时就不用再判断其余方案，直接通过goto跳出

主要代码讲解：

全排列函数 ：next_permutation(),用前需保证序列为升序

q[N]数组用处：q[n]中第i个位置储存的值对应着第a[q[i]]架飞机,

   举个简单的例子：有三架飞机编号 1，2，3

                              下降顺序有 1，2, 3

                                                 1, 3, 2

                                                 2, 1, 3

                                                 2, 3, 1

                                                3, 1,  2

                                                3,  2,  1
参考代码:

#includeusing namespace std;
const int N=20;
int t,n;
int q[N]={1,2,3,4,5,6,7,8,9,10};
struct point{
    int l,r,t;  //l为飞机最早下落时刻，r为飞机最晚下落时刻，t为飞机下落所需时间
}a[N];                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
int main()
{
    cin>>t;
    while(t--)
    {
    cin>>n;
    int t,d,l;
    for(int i=1;i<=n;i++){
    cin>>t>>d>>l;
    a[i].l=t;
    a[i].r=t+d;
    a[i].t=l;
    }
     
    do{
  int flag=1;
  int start=0;
  for(int i=0;i<n;i++)
       {
        start=max(start,a[q[i]].l);
        if(start<=a[q[i]].r)//这辆可以降落 
           {
           start+=a[q[i]].t;
           }
        else//这辆不可以降落，即整个方案不可行 
          {
           flag=0;
           break;
          }
        }
      if(flag==1) 
       {
        cout<<"YES"<<endl;
        goto p;
       }
    }while(next_permutation(q,q+n));
     
    cout<<"NO"<<endl;
    p:
    sort(q,q+10);//由于有多组数据，记得恢复q[N]
    }
    return 0;
}