作者:指针不指南吗
专栏:第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
-
用两个数组把 n 组 A、B存起来;
-
在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;
}
反思
- 取下限,直接可以使用
/
做到 - 数组最大能开多大
#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
当时考的时候,还是太紧张了,有点手忙脚乱的感觉,没有写出来,确实没有很难