1.数学公式
能练出b个,但练不出b+1个
可得出转换率v的式子:
a/(b+1)+1<v<=a/b
#include <iostream>
using namespace std;
int main()
{
int n,a,b;
int nmin=0,nmax=2e9; //int范围2e9多点
cin>>n;
while(n--)
{
cin>>a>>b;
int l=a/(b+1)+1;
int r=a/b;
nmin=max(nmin,l);
nmax=min(nmax,r);
}
cout<<nmin<<" "<<nmax;
return 0;
}
2.二分
对于每个ab,都有一个v的取值区间,最后的答案是取区间的交集
最大值可以枚举得出式子,最小值没推出来用二分求
#include <iostream>
#include <algorithm>
using namespace std;
int a,b;
int n;
int SL(int l,int r)
{
while(l<r)
{
int mid=l+r>>1;
if(a/mid<=b) r=mid;
else l=mid+1;
}
return l;
}
int main()
{
cin>>n;
int r=2e9,l=0;
while(n--)
{
cin>>a>>b;
r=min(r,a/b); //最大值
l=max(l,SL(1,2e9)); //最小值
}
cout<<l<<" "<<r;
return 0;
}