第14届蓝桥杯 | 冶炼金属

news/2024/10/11 17:34:48/

作者:指针不指南吗
专栏:第14届蓝桥杯真题

🐾慢慢来,慢慢来🐾

文章目录

  • 题目
  • 代码摸索
    • 第一次 AC 5/10
    • 第二次 AC 100%
  • 反思

题目

链接: 4956. 冶炼金属 - AcWing题库

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。

这个炉子有一个称作转换率的属性 V,V 是一个正整数,这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X,当普通金属 O 的数目不足 V 时,无法继续冶炼。

现在给出了 N 条冶炼记录,每条记录中包含两个整数 A 和 B,这表示本次投入了 A 个普通金属 O,最终冶炼出了 B 个特殊金属 X。

每条记录都是独立的,这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

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

输入格式

第一行一个整数 N,表示冶炼记录的数目。

接下来输入 N 行,每行两个整数 A、B,含义如题目所述。

输出格式

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

数据范围

对于 30% 的评测用例,1≤N≤ 1 0 2 10^2 102
对于 60% 的评测用例,1≤N≤ 1 0 3 10^3 103
对于 100% 的评测用例,1≤N≤ 1 0 4 10^4 104 ,1≤B≤A≤ 1 0 9 10^9 109

输入样例:

3
75 3
53 2
59 2

输出样例:

20 25

样例解释

当 V=20 时,有:[ 75 20 \frac{75}{20} 2075] =3,⌊ 53 20 \frac{53}{20} 2053⌋ =2,⌊ 59 20 \frac{59}{20} 2059⌋ =2,可以看到符合所有冶炼记录。

当 V=25 时,有:[ 75 25 \frac{75}{25} 2575] =3,⌊ 53 25 \frac{53}{25} 2553⌋ =2,⌊ 59 25 \frac{59}{25} 2559⌋ =2,可以看到符合所有冶炼记录。

且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。

代码摸索

第一次 AC 5/10

  1. 用两个数组把 n 组 A、B存起来;

  2. 在1~ 1 0 5 10^5 105 找到第一个满足条件的 V,即minV;

    1 0 5 10^5 105 ~1找到第一个满足条件的 V,即maxV;

把数据范围 N 卡在 $10^5,是因为在 1~ N之间遍历判断的,如果 1 0 9 10^9 109 样例调用famx地时候就会TLE ,更不行

每次遍历整个数据范围,O 很大,由这两点判断必须使用二分优化

#include<bits/stdc++.h>
using namespace std;const int N=1e5,M=1e4+10;int a[M]; //a存的是A
int b[M]; //b存的是Bint n; //q表示有几组数据//从小数到大数来寻找
int fmin(int a[],int b[])
{for(int i=1;i<N;i++)  //i表示转换率V{int flag=0;  //使用flag标志for(int j=0;j<n;j++)  //通过 j 来遍历数组中的元素{if(a[j]/i!=b[j])  flag=1; //只要有一个不满足就改变 flag 为1}if(flag==0) //全部满足,即找到所需要的,直接返回ireturn i;}
}//从大数往小数来寻找
int fmax(int a[],int b[])
{for(int i=N;i>=1;i--)  {int flag=0;for(int j=0;j<n;j++)  //数组{if(a[j]/i!=b[j])flag=1;}if(flag==0)return i;}
}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&a[i],&b[i]); //读入 n 组A,B}printf("%d %d",fmin(a,b),fmax(a,b)); //输出return 0;
}

第二次 AC 100%

二分优化

#include<bits/stdc++.h>
using namespace std;const int N=1e9,M=1e5+10;int a[M]; //a存的是A
int b[M]; //b存的是Bint n; //q表示有几组数据bool check1(int k)
{for(int j=0;j<n;j++)  //通过 j 来遍历数组中的元素{if(a[j]/k>b[j])return false;}return true;
}bool check2(int k)
{for(int j=0;j<n;j++)  //通过 j 来遍历数组中的元素{if(a[j]/k<b[j])return false;}return true;
}int main()
{scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&a[i],&b[i]);}int l=1,r=N;while(l<r){int mid=l+r>>1;if(check1(mid)) r=mid;else l=mid+1;}printf("%d ",l);l=1,r=N;while(l<r){int mid=l+r+1>>1;if(check2(mid)) l=mid;else r=mid-1;}printf("%d ",l);return 0;
}

反思

  1. 取下限,直接可以使用/做到
  2. 数组最大能开多大
#include<bits/stdc++.h>
using namespace std;
//在本人环境中
int c[20000][20000];
//全局数组能开到20000*20000int main()
{int b[100][100];	        // 函数中二维数组最大能开100*100char a[4* 518028];// 函数中的char数组最大能开4*518028int b1[500000];  // int最大能开到518028 return  0;
}

那么大的数据范围,就不应该去遍历,去尝试,应该直接二分

这个题是我后来自己做出来的,我哭死TvT

当时考的时候,还是太紧张了,有点手忙脚乱的感觉,没有写出来,确实没有很难

Alt


http://www.ppmy.cn/news/47032.html

相关文章

老宋 带你五分钟搞懂vue

Vue 1.1 什么是框架 任何编程语言在最初的时候都是没有框架的&#xff0c;后来随着在实际开发过程中不断总结『经验』&#xff0c;积累『最佳实践』&#xff0c;慢慢的人们发现很多『特定场景』下的『特定问题』总是可以『套用固定解决方案』。于是有人把成熟的『固定解决方案…

javascript之函数

什么是函数&#xff1f; &#xff08;函数是由事件驱动的或者当它被调用时执行的可重复使用的代码块。&#xff09; 是封装了一段可以重复调用执行的代码&#xff0c;通过找个代码块&#xff0c;能够实现大量代码的重复使用 使用函数的方式&#xff1a; 声明函数调用函数 声…

使用vscode+cmake进行c++代码编写

1. 前言 因为vcode的主题格式比visual studio好看&#xff0c;而且注释使用ctr/注释非常方便。所以对于一下小型的c代码测试&#xff0c;例如用不到外部库&#xff0c;只需要纯c自己语法&#xff0c;我就想和python一样&#xff0c;在vscode上写。因此记录一下比较简单的典型的…

C++算法初级10——动态规划

C算法初级10——动态规划 文章目录 C算法初级10——动态规划最优化问题动态规划分析流程和条件 最优化问题 生活中我们常常遇到这样一些问题&#xff1a; 看到上面的例子&#xff0c;我们发现这些问题都是在最大化&#xff08;或者最小化&#xff09;某个指标&#xff1a;最小…

剪枝与重参第七课:YOLOv8剪枝

目录 YOLOv8剪枝前言1.Overview2.Pretrain(option)3.Constrained Training4.Prune4.1 检查BN层的bias4.2 设置阈值和剪枝率4.3 最小剪枝Conv单元的TopConv4.4 最小剪枝Conv单元的BottomConv4.5 Seq剪枝4.6 Detect-FPN剪枝4.7 完整示例代码 5.YOLOv8剪枝总结总结 YOLOv8剪枝 前…

你真的会用iPad吗,如何使iPad秒变生产力工具?在iPad上用vscode写代码搞开发

目录 前言 视频教程 1. 本地环境配置 2. 内网穿透 2.1 安装cpolar内网穿透(支持一键自动安装脚本) 2.2 创建HTTP隧道 3. 测试远程访问 4. 配置固定二级子域名 4.1 保留二级子域名 4.2 配置二级子域名 5. 测试使用固定二级子域名远程访问 6. iPad通过软件远程vscode…

Java的时代依然还在,合格的Java工程师成为紧缺人才

Java的时代依然还在&#xff0c;合格的Java工程师成为紧缺人才 编程语言的世界变化莫测&#xff0c;在其中浮浮沉沉28年的Java&#xff0c;也经历见证了很多语言的兴起和衰败。在最新的编程语言排行榜中&#xff0c;Java依旧位居前三&#xff0c;可见Java的发展后劲有多强&…

C++linux高并发服务器项目实践 day3

Clinux高并发服务器项目实践 day3 文件IO标准C库IO函数与LinuxIO函数虚拟地址空间文件描述符Linux系统IO函数open与close mode:八进制的数&#xff0c;表示用户对创建出的新的文件的操作权限 最终的权限是&#xff1a;mode & ~umask 0777 r(读) w(写) x(可执行)都有这样的权…