蓝桥杯day3刷题日记--P9240 冶炼金属

P9240 [蓝桥杯 2023 省 B] 冶炼金属

经典二分，先在第一组中找到最小值，在利用最小值限制范围寻找最大值

#include <iostream>
#include <algorithm> 
using namespace std;
int n,kk;
int m[10001],num[10001];
int maxs,mins;bool check1(int x)
{for(int i=0;i<n;i++){if(m[i]/x>num[i]) return true;  一份的份额越小，对应的特殊金属越多，}                                   所以要收缩左边界return false;
}bool check2(int x)
{for(int i=0;i<n;i++){if(m[i]/x!=num[i]) return true;  份额越大，特殊金属越少，对应收缩右边界}return false;
}int main()
{cin>>n;kk=0;maxs=0,mins=1e9;for(int i=0;i<n;i++){cin>>m[i]>>num[i];kk=max(kk,m[i]/num[i]);}int l=0,r=kk;while(l+1<r){int mid=(l+r)/2;if(check1(mid)) l=mid;else r=mid;}mins=r;l=mins,r=kk;while(l+1<r){int mid=(l+r)/2;if(check2(mid)) r=mid;else l=mid;}maxs=l;printf("%d %d",mins,maxs);return 0;
}