AcWing 4956. 冶炼金属
原题链接
简单
作者:
ofs
,
2024-04-11 23:46:26
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define endl "\n"
using namespace std;
const int N=1e4+10;
int a[N],b[N];
int n;
//min
bool min(int mid)
{
//最小值左边的数会使得最后剩余的量还可以生产出特殊金属
//最小值右边的数就不会这样
int i;
for(i=0;i<n;i++)
{
if (a[i]/mid>b[i]) return false;
}
return true;
}
//max
bool max(int mid)
{
//最大值右边的数都会使得该数乘特殊金属的数量大于普通金属
int i;
for(i=0;i<n;i++)
{
if(mid*b[i]>a[i]) return false;
}
return true;
}
signed main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i];
}
//要求求最大值与最小值,则进行两次二分,每一次二分算其中一个值
//先算最小值
int l=1,r=1e9;
int mid;
while(l<r)
{
mid=l+r>>1;
if(min(mid))
r=mid;
else
l=mid+1;
}
cout<<l<<" ";
//算最大值
l=1,r=1e9;
mid=0;
while(l<r)
{
mid=l+r+1>>1;
if(max(mid))
l=mid;
else
r=mid-1;
}
cout<<l;
return 0;
}