蓝桥杯每日一题2023.9.7

落日映苍穹つ 2024-03-05 06:41 29阅读 0赞

[https://www.dotcpp.com/oj/problem3150.html][https_www.dotcpp.com_oj_problem3150.html]

### 题目描述 ###

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金

属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。

现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立

的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

### 分析 ###

求出符合条件的最大值最小值，可知用二分a\[i\] / mid > b\[i\]说明mid偏小，此处要求mid的最小值，需要满足a\[i\] / mid在<= b\[i\]的情况下,说明此时mid是偏大或等于的，将r = mid,求最大值同理

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    int n, a[N], b[N];
    bool check(int mid)
    {
    	for(int i = 1; i <= n; i ++)
    	{
    		if(a[i] / mid > b[i])return false;
    	}
    	return true;
    }
    bool ck(int mid)
    {
    	for(int i = 1; i <= n; i ++)
    	{
    		if(a[i] / mid < b[i])return false;
    	}
    	return true;
    }
    int main()
    {
    	cin >> n;
    	for(int i = 1; i <= n; i ++)
    	{
    		cin >> a[i] >> b[i];
    	}
    	int l = 0, r = 1e9;
    	while(l + 1 != r)
    	{
    		int mid = (l + r) >> 1;
    		if(check(mid))r = mid;
    		else l = mid;
    	}
    	cout << r << ' ';
    	int ll = 0, rr = 1e9 + 10;
    	while(ll + 1 != rr)
    	{
    		int mid = (ll + rr) >> 1;
    		if(ck(mid))ll = mid;
    		else rr = mid;
    	}
    	cout << ll;
    	return 0;
    }

[https_www.dotcpp.com_oj_problem3150.html]: https://www.dotcpp.com/oj/problem3150.html