点击题目连接
题目描述
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性，是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X。当普通金属 O 的数目不足 V 时，无法继续冶炼。
现在给出了 n 条冶炼记录，每条记录中包含两个整数 a 和 b，这表示本次投入了 a 个普通金属 O，最终冶炼出了 b 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
根据这 n 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
输入格式
第一行一个整数 n，表示冶炼记录的数目。
接下来输入 n 行，每行两个整数 A 和 B，含义如题目所述。
输出格式
输出两个整数，分别表示 V 可能的最小值和最大值，中间用空格分开。
输入输出样例
输入 #1
3
75 3
53 2
59 2
输出 #1
20 25
说明/提示
【评测用例规模与约定】
- 对于 30% 的评测用例，n ≤ 10。
- 对于 60% 的评测用例，n ≤ 1000。
- 对于 100% 的评测用例，n ≤ 10000，1 ≤ a ≤ 1e9，1 ≤ b ≤ 1e9。
一、问题分析
我们知道，一个合法的转换率v值，对于每条记录，应该满足以下条件：
a/v = b
- 当v过大时，a/v < b，即a金属不够
- 当v过小时，a/v > b，即a金属有剩
实际上，对于每条记录都能确定一段合法的转换率v区间，我们的目标是找到所有可能的v值合法区间中的最小值和最大值，类似二分答案里的求左/右边界。
二、解题思路
二分答案
- 二分答案可行性
推测转换率v的范围，从范围n ≤ 10000，1 ≤ a ≤ 1e9，1 ≤ b ≤ 1e9可以知道，v最大为1e9，如果我们用O(n)遍历的话，明显会超时，这时候我们可以考虑用二分答案，我们可以使用二分查找来确定v的可能范围。对于每个可能的v值，我们需要检查它是否满足所有记录的条件。
- 二分答案的条件
我们都知道，用二分答案时，对于数列中的“值”需要有顺序，其实这题的v其实在一定条件上也是有序的，如图
- 当我们求右边界vmax的时候，v的范围就分成了两部分，（1，vmax）和（vmax， 1e9），其中判断条件分别为a/v >= b和a/v < b。
- 求左边界也是类似。
二分答案求左右边界模版
在我之前的博客有讲过，感兴趣的可以去了解一下！
博文链接
三、代码实现
#include<bits/stdc++.h>
using namespace std;
int N;
int A[10005]={0};
int B[10005]={0};
bool c_right(int x)
{for(int i=0;i<N;++i){if(A[i]/x < B[i]) return false;}return true;
}
bool c_left(int x)
{for(int i=0;i<N;++i){if(A[i]/x > B[i]) return false;}return true;
}
int main()
{cin>>N;for(int i=0;i<N;++i) cin>>A[i]>>B[i];//找右边界int l=1,r=1000000000,mid=0;//找右边界while(l<=r){mid = (l+r) >> 1;if(c_right(mid)){l = mid + 1;}else r = mid - 1;}int max = r;l=1,r=1000000000,mid=0;//找左边界while(l<=r){mid = (l+r) >> 1;if(c_left(mid)){r = mid - 1;}else l = mid + 1;}int min = l;cout<<min<<" "<<max;return 0;
}
通过本次博客，我们不仅解决了“冶炼金属”问题，还深入理解了二分答案算法的应用场景和实现方法。希望读者能够掌握这一高效算法，并在类似问题中灵活运用。
如果你有任何问题或建议，欢迎在评论区留言。让我们一起探索算法的无限可能！