3、冶炼金属
题目 冶炼金属
思路分析
v个o可以冶炼出一个x
令o为o的个数 x为x的个数
其实就有o/v=x
这个v可以取到很多 比如o=75时 x=3时 v可以取20~25
有明显的满足条件的范围 典型二分问题
我可以对每组询问都二分去求出v*min 和 v*max
但是答案应该是满足所有情况的 那就是要取交集
也就是说要在所有的v*min里面找一个最大的 所有的v*max里找一个最小的
用这两句实现即可
\(vmin=max(vmin,findleft(o,x)); vmax=min(vmax,findright(o,x));\)重点在于怎么二分找到这个v*min和v*max
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
int maxv=1e9,minv=1;
while(n--){
int A,B;cin>>A>>B;
int l=1,r=A;
while(l<r){
int m=l+r>>1;
if(A/m<=B) r=m;
else l=m+1;
}
minv=max(minv,r);
l=1,r=A;
while(l<r){
int m=l+r+1>>1;
if(A/m>=B) l=m;
else r=m-1;
}
maxv=min(maxv,r);
}
cout<<minv<<" "<<maxv;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int findleft(int o,int x)
{
int l=1,r=1e9;
while(l<r)
{
int mid=l+r>>1;
if(o/mid<=x)
r=mid;
else
l=mid+1;
}
return r;
}
int findright(int o,int x)
{
int l=1,r=1e9;
while(l<r)
{
int mid=l+r+1>>1;
if(o/mid>=x)
l=mid;
else
r=mid-1;
}
return r;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;
cin>>n;
int v_min=1,v_max=1e9;
while(n--)
{
int o,x;
cin>>o>>x;
v_min=max(v_min,findleft(o,x));
v_max=min(v_max,findright(o,x));
}
cout<<v_min<<" "<<v_max;
return 0;
}
💬 评论