P9240 [蓝桥杯 2023 省 B] 冶炼金属：二分模型

目录

二分模型

代码 

题目链接放着啦。 

P9240 [蓝桥杯 2023 省 B] 冶炼金属

二分模型应用

主要是想说一下这道题的二分思想。

由题意我们可以知道：转化率V=A/B，转化一下，A / V = B ，转化成以A B为参数的式子。对于这样的式子要有一点敏锐，其具有单调性。由此可以想到抽象出二分模型。

我们可以把转化率当成以这两个参数为横纵坐标的图形的斜率。这样看的话，对于每一组数据给出的A B，我们都可以得出一个满足条件的V的集合。最后再对集合取交集(可以直接用max/min函数实现，不一定要记录下整个集合)即可得出答案。

由图像我们可以发现，我们要求的是两个边界点，想一下二分模板比较明显的题目是求一个数据在序列中的起始位置和终止位置，有点感觉了吧？[我是后来又看二分模板题的时候想起来的，才发现这道题这么符合二分😂]

之前写过的文章~

【第三课】整数二分(acwing-789-含思路详解，死循环问题，while循环出口问题）

推荐遇到相关算法的题目可以正好回顾一下当时比较基础直白的题目。 

想清楚这道题是怎么简化成二分模型的。

我们要求的是V，也就是说这个序列是V的从小到大排列的序列。

那么最小值也就是：从左向右看第一个使得 A/V>=B的值  得左边界

最大值是从左向右看第一个使得A/V<=B-1的值 再减去1  因为<=B-1的最后一个值是分段图像里B的下面那一段(B-1段)对应的V的第一个点，我们要找的是B对应的的最后一个点。

我们这样看的话，这道题只用到了二分的模板一，也就是求左边界的模板。

我们当然也可以用上面所说的类似求起始位置和终止位置的题那样，把题目看成

找到 第一个使得 A/V>=B 的第一个值 和 最后一个使得 A/V>B-1 的值 细品，有点绕。

y总的讲解，也有对数学方法的讲解。

AcWing 4956. 冶炼金属（春季每日一题2023）

代码 

①只使用一个模板 

#include<iostream>
#include<algorithm>
using namespace std;
int get(int a,int b)
{
	int l=1;
	int r=1e9+1;//避免参数b=0时，结果的冲突 
	
	while(l<r)
	{
		int mid=(l+r)/2;
		if(a/mid<=b)r=mid;
		else l=mid+1;
	}
	return l;
}
int main()
{
	int n;
	scanf("%d",&n);
	int Min=1,Max=1e9;//根据A/V=B得出V的范围
	while(n--)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		Min=max(Min,get(a,b));//求这 n 组数据满足的最小值的交集 
		Max=min(Max,get(a,b-1)-1);//最大值 
	}
	printf("%d %d",Min,Max);
	return 0;
 } 

②使用两个模板

#include<iostream>
#include<algorithm>
using namespace std;
int get(int a,int b)
{
	int l=1;
	int r=1e9+1;//避免参数b=0时，结果的冲突 
	
	while(l<r)
	{
		int mid=(l+r)/2;
		if(a/mid<=b)r=mid;
		else l=mid+1;
	}
	return l;
}
int get2(int a,int b)
{
	int l=1;
	int r=1e9+1;//避免参数b=0时，结果的冲突 
	
	while(l<r)
	{
		int mid=(l+r+1)/2;
		if(a/mid>b-1)l=mid;
		else r=mid-1;
	}
	return l;
 } 
int main()
{
	int n;
	scanf("%d",&n);
	int Min=1,Max=1e9;
	while(n--)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		Min=max(Min,get(a,b));//求这 n 组数据满足的最小值的交集 
		Max=min(Max,get2(a,b));//最大值 
	}
	printf("%d %d",Min,Max);
	return 0;
 } 

就写到这里啦。 

有问题欢迎指出，一起加油！！！