AcWing 4956. 冶炼金属
原题链接
简单
作者:
修仙修仙
,
2024-03-01 19:06:18
,
所有人可见
,
阅读 24
#先找出最大值,经过观察可知a[i]/b[i]的最小值就是最大值,然后对最小值进行二分查找
#查找满足a[i]/mid==b[i]的最小值
#二分的区间满足单调性和二段性,存在一段区间满足a[i]/x==b[i],其中x属于这段区间,
#观察可知,当x越小就会导致a[i]/b[i]越大,反之就会越小,这样就达到了单调性,当x在某
#一范围内a[i]/x==b[i],小于这个区间的x就会a[i]/b[i]>x,大于这个区间就会a[i]/b[i]<x,
#这就达到了二段性,这题与luogo p2440
#的方法很像,链接: http://www.luogu.com.cn/problem/P2440
#include<iostream>
using namespace std;
int n;
int maxx=0x3f3f3f3f;
const int N=1e5+5;
int a[N],b[N];
bool check(int x)
{
for (int i=1;i<=n;i++)
{
if(a[i]/x>b[i])return 0;
}
return 1;
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
maxx=min(a[i]/b[i],maxx);
}
int l=1,r=maxx;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l<<" "<<maxx<<"\n";
return 0;
}