（蓝桥杯第十四届c解法，部分题目）​一、冶炼金属​二、飞机降落_冶炼金属蓝桥杯

2023年第十四届蓝桥杯大赛软件类省赛C/C++大学B组真题

一、冶炼金属

题目：

问题描述

小蓝有一个神奇的炉子用于将普通金属 OO 冶炼成为一种特殊金属 XX。这个炉子有一个称作转换率的属性 VV，VV 是一个正整数，这意味着消耗 VV 个普通金属 OO 恰好可以冶炼出一个特殊金属 XX，当普通金属 OO 的数目不足 VV 时，无法继续冶炼。

现在给出了 NN 条冶炼记录，每条记录中包含两个整数 AA 和 BB，这表示本次投入了 AA 个普通金属 OO，最终冶炼出了 BB 个特殊金属 XX。每条记录都是独立的，这意味着上一次没消耗完的普通金属 OO 不会累加到下一次的冶炼当中。

根据这 NN 条冶炼记录，请你推测出转换率 VV 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 NN，表示冶炼记录的数目。

接下来输入 NN 行，每行两个整数 AA、BB，含义如题目所述。

输出格式

输出两个整数，分别表示 VV 可能的最小值和最大值，中间用空格分开。

样例输入

3
75 3
53 2
59 2

样例输出

20 25

样例说明

当 V=20V=20 时，有：⌊7520⌋=3⌊2075​⌋=3，⌊5320⌋=2⌊2053​⌋=2，⌊5920⌋=2⌊2059​⌋=2，可以看到符合所有冶炼记录。

当 V=25V=25 时，有：⌊7525⌋=3⌊2575​⌋=3，⌊5325⌋=2⌊2553​⌋=2，⌊5925⌋=2⌊2559​⌋=2，可以看到符合所有冶炼记录。

且再也找不到比 2020 更小或者比 2525 更大的符合条件的 VV 值了。

评测用例规模与约定

对于 3030% 的评测用例，1≤N≤1021≤N≤102。

对于 6060% 的评测用例，1≤N≤1031≤N≤103。

对于 100100% 的评测用例，1≤N≤1041≤N≤104，1≤B≤A≤1091≤B≤A≤109。

题解：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int main(int argc, char *argv[])
{
  int a,b,n,c,d;
  int max=INT_MAX;
  int min=-1;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d %d",&a,&b);
    c=a/b;
    if(c<max){
      max=c;
    }
    d=a/(b+1)+1;
    if(d>min){
      min=d;
    }
  }
  printf("%d %d",min,max);
  return 0;
}

二、飞机降落

题目：

问题描述

NN 架飞机准备降落到某个只有一条跑道的机场。其中第 ii 架飞机在 TiTi​ 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 DiDi​ 个单位时间，即它最早可以于 TiTi​ 时刻开始降落，最晚可以于 Ti+DiTi​+Di​ 时刻开始降落。降落过程需要 LiLi​ 个单位时间。

一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

请你判断 NN 架飞机是否可以全部安全降落。

输入格式

输入包含多组数据。

第一行包含一个整数 TT，代表测试数据的组数。

对于每组数据，第一行包含一个整数 NN。

以下 NN 行，每行包含三个整数：TiTi​，DiDi​ 和 LiLi​。

输出格式

对于每组数据，输出 YESYES 或者 NONO，代表是否可以全部安全降落。

样例输入

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

样例输出

YES
NO

样例说明

对于第一组数据，可以安排第 33 架飞机于 00 时刻开始降落，2020 时刻完成降落。安排第 22 架飞机于 2020 时刻开始降落，3030 时刻完成降落。安排第 11 架飞机于 3030 时刻开始降落，4040 时刻完成降落。

对于第二组数据，无论如何安排，都会有飞机不能及时降落。

评测用例规模与约定

对于 3030% 的数据，N≤2N≤2。

对于 100100% 的数据，1≤T≤101≤T≤10，1≤N≤101≤N≤10，0≤Ti,Di,Li≤1050≤Ti​,Di​,Li​≤105。

#include<bits/stdc++.h>
using namespace std;
const int N=15;
 
int t,n;
//t:测试数据次数
//n:n架飞机 
bool flag,visit[N];
//第n架飞机是否在dfs中被访问
//flag: 用于判断全部飞机是否能降落 
 
struct p
{
    int time,delay,land; 
};
//p:结构体p表示飞机的信息
 
 
void dfs(int cnt,int last,vector<p>v)
{
    if(!cnt)
    {
        flag=true;
        return;
    }
    //如果访问个数已经=飞机架数,说明所有飞机可以降落，跳出循环 
    
    for(int i=1;i<=n;i++)
    {
        if(!visit[i] && v[i].time+v[i].delay >= last)
        //若这架飞机还没被访问,且这架飞机的最长等待时间>上一架飞机完成降落的时间
        //则继续dfs 
        {
            visit[i]=true;
            dfs(cnt-1,max(last,v[i].time)+v[i].land,v);
            //下一次dfs的last=max(上架飞机完成降落的时间,这架飞机到达的时间)+这架飞机完成降落的时间
            visit[i]=false;
            //回溯 
        }
    }
    //若无法完成降落,flag还是false 
}
 
 
int main()
{
    cin >> t;
    while(t--)
    {
        memset(visit,false,sizeof(visit));
        ///每次询问需要重置visit数组
        cin >> n;
        vector<p>v(N);
        //v数组即p数组 
        for(int i=1;i<=n;i++)
        {
            cin >> v[i].time >> v[i].delay >> v[i].land;
        } 
        flag=false;
        //每次访问重置flag 
        dfs(n,0,v); 
        if(flag)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}

下面是逐行详细解释代码的含义：

下面是逐行详细解释代码的含义：
 
#include<bits/stdc++.h>：这行代码包含了一个头文件，其中包含了所有的标准库文件。这是一个快捷方式，可以包含常用的库。
 
using namespace std;：这行代码允许你使用标准库的函数和对象，而无需指定std::前缀。
 
const int N=15;：这行代码定义了一个常量变量N，其值为15。它表示最大飞机数量。
 
int t,n;：这行代码声明了两个整数变量t和n。t表示测试用例的数量，n表示飞机的数量。
 
bool flag,visit[N];：这行代码声明了两个布尔变量flag和visit，其中visit是一个大小
为N的数组。flag用于确定是否所有飞机都可以降落，visit用于跟踪飞机在DFS遍历中是否被访问过。
 
struct p { int time, delay, land; };：这行代码定义了一个结构体p，表示飞机的信息。
它有三个整数成员：time（飞机到达时间）、delay（飞机允许的最大延误时间）和land
（飞机降落所需时间）。
 
void dfs(int cnt, int last, vector<p> v)：这行代码定义了一个递归函数dfs，
执行深度优先搜索。它接受三个参数：cnt（尚未访问的飞机数量）、last（上一架飞机降落的时间）
和v（飞机信息的向量）。
if (!cnt) { flag = true; return; }：这行代码检查是否所有飞机都已经访问过（cnt为零）。
如果是，则将flag设置为true，并从函数中返回，表示所有飞机都可以降落。
 
for (int i = 1; i <= n; i++)：这行代码开始一个循环，遍历所有的飞机。
 
if (!visit[i] && v[i].time + v[i].delay >= last)：这行代码检查当前飞机i
是否尚未访问过（!visit[i]），并且其到达时间和最大延误时间之和是否大于等于
上一架飞机降落的时间。如果两个条件都满足，则飞机可以降落。
 
visit[i] = true;：这行代码将当前飞机标记为已访问。
 
dfs(cnt - 1, max(last, v[i].time) + v[i].land, v);：这行代码使用更新后的参数
对dfs进行递归调用。它将未访问飞机数量减少一（cnt - 1），将上一架飞机降落时间更新
为当前最大时间和当前飞机到达时间的较大值（max(last, v[i].time)），并加上当前飞机
的降落时间（v[i].land）。
 
visit[i] = false;：这行代码将当前飞机标记为未访问（回溯）。
 
int main()：这行代码开始主函数。
cin >> t;：这行代码从输入中读取测试用例的数量。
 
while (t--)：这行代码开始一个循环，循环t次。
 
memset(visit, false, sizeof(visit));：这行代码将visit数组重置为全部为
false的值。它确保在每个测试用例之前，没有飞机被标记为已访问。
 
cin >> n;：这行代码从输入中读取当前测试用例的飞机数量。
 
vector<p> v(N);：这行代码创建了一个大小为N的向量v，用于存储飞机的信息。
 
for (int i = 1; i <= n; i++)：这行代码开始一个循环，读取每架飞机的信息。
 
cin >> v[i].time >> v[i].delay >> v[i].land;：这行代码从输入中读取当前
飞机的到达时间、最大延误时间和降落时间，并将它们存储在向量v中。
 
flag = false;：这行代码在每个测试用例之前将flag变量重置为false。
 
dfs(n, 0, v);：这行代码调用dfs函数执行深度优先搜索，初始参数为剩余n架飞机、
上一架飞机降落时间为0，以及包含飞机信息的向量v。
 
60-64. 这几行代码检查flag的值，并输出"YES"表示所有飞机都可以降落，或输出"NO"表示不能。
 
return 0;：这行代码结束主函数，并返回0以表示程序执行成功。