题目分析描述
投入了 A个普通金属 O,最终冶炼出了 B个特殊金属 X。推测出转换率V的最小值和最大值分别可能是多少?
设转换率的属性V=x,(含义:每x个普通金属O转成1个特殊金属X)
对于任意一组冶炼记录:
一共投入A个普通金属O,B个特殊金属X,则
x * B <=A < (B+1)*x
解得: A/(B+1)<x<=A/B
取整得 A/(B+1)+1<=x<=A/B
说明: 要想最终只转成B个特殊金属,普通金属的数量就不足以制作B+1个特殊金属,并且x取整
对于所有冶炼记录:
就是求多组x的解区间的交集,左边界取A/(B+1)+1的最大值,右边界取A/B的最小值
如样例为
3*x<=75<4*x
2*x<=53<3*x
2*x<=59<3*x
解得:
18<x<=25
17<x<=26
19<x<=29
求区间交集
19<x<=25
取整后x_min=20,x_max=25
C++代码
时间复杂度O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,rmax=2e9,rmin=-2e9;
int main(){
int a,b;
cin>>n;
while(n--){
scanf("%d%d",&a,&b);
rmax=min(rmax,a/b);
rmin=max(rmin,a/(b+1)+1);
}
cout<<rmin<<' '<<rmax<<endl;
return 0;
}