(蓝桥杯第十四届c解法,部分题目)​一、冶炼金属​二、飞机降落

2023-11-06 21:30

本文主要是介绍(蓝桥杯第十四届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以表示程序执行成功。

这篇关于(蓝桥杯第十四届c解法,部分题目)​一、冶炼金属​二、飞机降落的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/359157

相关文章

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

笔记整理—内核!启动!—kernel部分(2)从汇编阶段到start_kernel

kernel起始与ENTRY(stext),和uboot一样,都是从汇编阶段开始的,因为对于kernel而言,还没进行栈的维护,所以无法使用c语言。_HEAD定义了后面代码属于段名为.head .text的段。         内核起始部分代码被解压代码调用,前面关于uboot的文章中有提到过(eg:zImage)。uboot启动是无条件的,只要代码的位置对,上电就工作,kern

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

项目实战系列三: 家居购项目 第四部分

购物车 🌳购物车🍆显示购物车🍆更改商品数量🍆清空购物车&&删除商品 🌳生成订单 🌳购物车 需求分析 1.会员登陆后, 可以添加家居到购物车 2.完成购物车的设计和实现 3.每添加一个家居,购物车的数量+1, 并显示 程序框架图 1.新建src/com/zzw/furns/entity/CartItem.java, CartItem-家居项模型 /***

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

码蹄集部分题目(2024OJ赛9.4-9.8;线段树+树状数组)

1🐋🐋配对最小值(王者;树状数组) 时间限制:1秒 占用内存:64M 🐟题目思路 MT3065 配对最小值_哔哩哔哩_bilibili 🐟代码 #include<bits/stdc++.h> using namespace std;const int N=1e5+7;int a[N],b[N],c[N],n,q;struct QUERY{int l,r,id;}que

关于断言的部分用法

1、带变量的断言  systemVerilog assertion 中variable delay的使用,##[variable],带变量的延时(可变延时)_assertion中的延时-CSDN博客 2、until 的使用 systemVerilog assertion 中until的使用_verilog until-CSDN博客 3、throughout的使用   常用于断言和假设中的