目录
题目：
题目描述：
题目链接：
思路：
核心思路：
思路详解：
代码：
代码详解：
题目：
题目描述：
题目链接：
蓝桥云课 冶炼金属
洛谷 P9240 [蓝桥杯 2023 省 B] 冶炼金属
思路：
核心思路：
整数二分的两个模板
思路详解：
由题求转换率V的最小值和最大值，结合题意不难发现存在单调性和二段性。见到同时求V的最小值和最大值，第一想法就是整数二分的两个模板。两次二分,一次求v的最小值,一次求v的最大值
代码：
代码详解：
#include<bits/stdc++.h> //自己做的时候第一思路就是整数二分的两个模板
using namespace std; //两次二分,一次求v的最小值,一次求v的最大值 int a,b;
int n;
int vmin=-1;
int vmax=1e9;int main()
{cin>>n;while(n--) //n行输入数据 {int a,b;scanf("%d %d",&a,&b);int l1=1; //由题1<=b<=a<=10^9,a/v=b,所以1<=v<=10^9,左右边界可以确定 int r1=1e9;while(l1<r1){int mid=l1+r1>>1; //先求满足每行数据v的最小值,这里用的第一个模板 if(a/mid<=b) //这里是模板的check(mid),mid>=v,由题a/v=b,所以a/mid<=b {r1=mid;}else{l1=mid+1;}}if(l1>vmin) //输入n行数据,即有n个l1,每次的l1都是满足该行数据的最小v,但是由题vmin要满足 { //所有行的数据,所以vmin是l1里面的最大值 vmin=l1;}int l2=1;int r2=1e9;while(l2<r2){int mid=l2+r2+1>>1; //再求满足每行数据v的最大值,这里用的第二个模板 if(a/mid>=b) //这里是模板的check(mid),mid<=v,由题a/v=b,所以a/mid>=b {l2=mid;}else{r2=mid-1; //记忆小技巧,如果这里有-1上面mid那里就补个+1 }}if(l2<vmax) //输入n行数据,即有n个l2,每次的l2都是满足该行数据的最大v,但是由题vmax要满足 { //所有行的数据,所以vmax是l2里面的最小值 vmax=l2;}}printf("%d %d",vmin,vmax);return 0;
}
