蓝桥杯 冶炼金属

原题目链接

---

🔧 冶炼金属转换率推测题解

📜 原题描述

小蓝有一个神奇的炉子用于将普通金属 $O$ 冶炼成为一种特殊金属 $X$。这个炉子有一个属性叫转换率 $V$，是一个正整数，表示每 $V$ 个普通金属 $O$ 可以冶炼出 1 个特殊金属 $X$。

有 $N$ 条冶炼记录，每条记录包含两个整数 $A$ 和 $B$，表示本次使用了 $A$ 个普通金属 $O$，冶炼出了 $B$ 个特殊金属 $X$。

每次冶炼是独立的，剩余金属不会带到下一次。

现在，请你根据所有冶炼记录推测转换率 $V$ 的最小可能值和最大可能值。

题目保证有解。

---

🧾 输入格式

第一行：整数 N（1 ≤ N ≤ 10^4）接下来的 N 行：每行两个整数 A, B（1 ≤ B ≤ A ≤ 10^9）

---

📤 输出格式

输出两个整数，表示可能的最小转换率 $V$ 和最大转换率 $V$，用空格隔开。

---

🧪 输入样例

3
75 3
53 2
59 2

✅ 输出样例

20 25

---

💡 思路解析（基于你的代码）

本题要求找出使得每条记录都满足 $\lfloor \frac{A_i}{V}\rfloor =B_i$ 的所有 $V$，并输出其中的最小值和最大值。

你使用了两次二分查找：

• 第一次查最小合法 $V$（尽可能小）；
• 第二次查最大合法 $V$（尽可能大）。

🔁 判定逻辑：

• 对于每个中间值 $mid$，用 arr[i][0] / mid 与 arr[i][1] 做比较：
  • 如果大于 $B_i$，说明 $mid$ 太小了，要增大；
  • 如果小于 $B_i$，说明 $mid$ 太大了，要减小；
  • 否则说明该 $mid$ 是合法值。

---

📐 算法解析

1. 设定二分范围 $[1,\max A_i]$；
2. 第一次二分找出满足条件的最小合法 $V$；
3. 第二次二分找出满足条件的最大合法 $V$；
4. 输出这两个值。

时间复杂度：

• 每次二分最多 $\log (10^9)$ 次；
• 每次判断遍历 $N$ 条记录；
• 总体复杂度约为 $O(N\log A_{max})$。

---

💻 完整代码（原封不动）

#include<bits/stdc++.h>using namespace std;int main() {int N;cin >> N;vector<vector<int>> arr(N, vector<int>(2));int l = 1, r = 1, res1 = INT_MAX, res2 = INT_MIN, r_l, r_r;for (int i = 0; i < N; i++) cin >> arr[i][0] >> arr[i][1], r = max(r, arr[i][0]);r_l = l, r_r = r;while(r_l <= r_r) {int mid = (r_l + r_r) / 2;int code = 0;for (int i = 0; i < N && code == 0; i++) {if (arr[i][0] / mid > arr[i][1]) code = 1;if (arr[i][0] / mid < arr[i][1]) code = 2;}if (code == 0) res1 = min(res1, mid);if (code == 1) r_l = mid + 1;else r_r = mid - 1;}r_l = l, r_r = r;while(r_l <= r_r) {int mid = (r_l + r_r) / 2;int code = 0;for (int i = 0; i < N && code == 0; i++) {if (arr[i][0] / mid > arr[i][1]) code = 1;if (arr[i][0] / mid < arr[i][1]) code = 2;}if (code == 0) res2 = max(res1, mid);if (code == 2) r_r = mid - 1;else r_l = mid + 1;}cout << res1 << " " << res2;return 0;
}//by wqs

---

✅ 总结

这段代码巧妙地用了二分查找解决最大/最小合法值问题。

• 第一次二分是找下界（合法的最小值）；
• 第二次二分是找上界（合法的最大值）；
• 每次判断只要符合全部记录，就尝试更新答案。

这种思路比直接取不等式交集更通用，也适用于更复杂的分段函数类问题。

---