方法一:二分法
#include<iostream>
#include<algorithm>
using namespace std;
int get(int x,int y)
{
int l=1,r=1e9+1;
while(l<r)
{
int mid=l+r>>1;
if(x/mid<=y) r=mid;
else l=mid+1;
}
return l;
}
int main()
{
int n;
cin>>n;
int vmin=1,vmax=1e9;//V是一个正整数,最小值为1,又A<=1e9,(A/V)=B>=1,因此V最大为1e9,
while(n--)
{
int x,y;
scanf("%d%d",&x,&y);
vmin=max(vmin,get(x,y));
vmax=min(vmax,get(x,y-1)-1);
//要算公共解,有的数据Vmin比另一个数据Vmin大,即小的Vmin不适用于全体数据,故取其中的最大值
//Vmax同理
}
cout<<vmin<<' '<<vmax<<endl;
return 0;
}
方法二:数学思想
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin>>n;
int vmin=1,vmax=1e9;
while(n--)
{
int x,y;
scanf("%d%d",&x,&y);
vmin=max(vmin,x/(y+1)+1);
vmax=min(vmax,x/y);
}
cout<<vmin<<' '<<vmax<<endl;
return 0;
}