AcWing 4956. 冶炼金属
原题链接
简单
作者:
見
,
2024-04-11 12:38:39
,
所有人可见
,
阅读 3
二分 O(Nlog(n))
#include<bits/stdc++.h>
using namespace std;
int T,a,b;
int Vmin=1,Vmax=1e9;
int get_Vmin(int a,int b)
{
int l=1,r=a+1;
while(l<r)
{
int mid =l+r>>1;
if(a/mid<=b)r=mid;
else l=mid+1;
}
return l;
}
int main()
{
cin>>T;
while(T--)
{
cin>>a>>b;
Vmin=max(Vmin,get_Vmin(a,b));
Vmax=min(Vmax,get_Vmin(a,b-1)-1);
}
cout<<Vmin<<" "<<Vmax;
}
公式 O(n)
#include<bits/stdc++.h>
using namespace std;
int T,a,b;
int Vmin=1,Vmax=1e9;
int main()
{
cin>>T;
while(T--)
{
cin>>a>>b;
Vmin=max(Vmin,a/(b+1)+1);
Vmax=min(Vmax,a/b);
}
cout<<Vmin<<" "<<Vmax;
}