蓝桥杯day3刷题日记--P9240 冶炼金属

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

经典二分，先在第一组中找到最小值，在利用最小值限制范围寻找最大值

#include <iostream>
#include <algorithm> 
using namespace std;
int n,kk;
int m[10001],num[10001];
int maxs,mins;

bool check1(int x)
{
	for(int i=0;i<n;i++)
	{
		if(m[i]/x>num[i]) return true;  一份的份额越小，对应的特殊金属越多，
	}                                   所以要收缩左边界
	return false;
}

bool check2(int x)
{
	for(int i=0;i<n;i++)
	{
		if(m[i]/x!=num[i]) return true;  份额越大，特殊金属越少，对应收缩右边界
	}
	return false;
}

int main()
{
	cin>>n;
	kk=0;
	maxs=0,mins=1e9;
	for(int i=0;i<n;i++)
	{
		cin>>m[i]>>num[i];
		kk=max(kk,m[i]/num[i]);
	}
	
	int l=0,r=kk;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(check1(mid)) l=mid;
		else r=mid;
	}
	mins=r;
	
	l=mins,r=kk;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(check2(mid)) r=mid;
		else l=mid;
	}
	maxs=l;
	printf("%d %d",mins,maxs);
	return 0;
}