【二分查找, 数学】冶炼金属【十四届蓝桥杯省赛CB】

题目

4956. 冶炼金属 - AcWing题库

蓝桥杯2023年第十四届省赛真题-冶炼金属 - C语言网

---

小蓝有一个神奇的炉子用于将普通金属 $O$ 冶炼成为一种特殊金属 $X$ 。

这个炉子有一个称作转换率的属性 $V$ ， $V$ 是一个正整数，这意味着消耗 $V$ 个普通金属 $O$ 恰好可以冶炼出一个特殊金属 $X$ ，当普通金属 $O$ 的数目不足 $V$ 时，无法继续冶炼。

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

每条记录都是独立的，这意味着上一次没消耗完的普通金属 $O$ 不会累加到下一次的冶炼当中。

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

输入格式

第一行一个整数 $N$ ，表示冶炼记录的数目。

接下来输入 $N$ 行，每行两个整数 $A、B$ ，含义如题目所述。

输出格式

输出两个整数，分别表示 $V$ 可能的最小值和最大值，中间用空格分开。

数据范围

对于 $30\%$ 的评测用例， $1 ≤ N ≤ 10^2$ 。
对于 $60\%$ 的评测用例， $1 ≤ N ≤ 10^3$ 。
对于 $100\%$ 的评测用例， $1 ≤ N ≤ 10^4$ ， $1 ≤ B ≤ A ≤ 10^9$ 。

输入样例：

3
75 3
53 2
59 2

输出样例：

20 25

样例解释

当 $V = 20$ 时，有： $⌊\frac{75}{20} ⌋ = 3$ ， $⌊\frac{53}{20} ⌋ = 2$ ， $⌊\frac{59}{20} ⌋ = 2$ ，可以看到符合所有冶炼记录。

当 $V = 25$ 时，有： $⌊\frac{75}{25} ⌋ = 3$ ， $⌊\frac{53}{25} ⌋ = 2$ ， $⌊\frac{59}{25} ⌋ = 2$ ，可以看到符合所有冶炼记录。

且再也找不到比 $20$ 更小或者比 $25$ 更大的符合条件的 $V$ 值了。

解题

方法一：二分查找

思路

由题意可知，我们需要找出 $V_{min}$ 与 $V_{max}$ ，使得 $\lfloor \frac{A_i}{V} \rfloor = B_i$ （其中 $i = 1\dots{N}, \enspace V \in[V_{min}, V_{max}]$ ）。

由于每条冶炼记录都是独立的，要使所有冶炼记录都成立， $V$ 的范围就应是所有 $V_i$ 的交集，也就是说： $V_{min} = \max(V_{1_{min}}, V_{2_{min}}, \dots, V_{N_{min}}), \enspace V_{max} = \min(V_{1_{max}}, V_{2_{max}}, \dots, V_{N_{max}})$ 。

对于第 $i$ 条冶炼记录，$\frac{A_i}{V_i}$ 是单调的（ $V_i \uparrow, \frac{A_i}{V_i} \downarrow$ ），所以 $V_i$ 的上界与下界可以借助二分查找找出来。

代码

#include <iostream>

using namespace std;

int n, a, b;

int main() {
    scanf("%d", &n);
    int vmn = 1, vmx = 2e9;
    while (n--) {
        scanf("%d%d", &a, &b);
        int l = 1, r = 2e9;
        while (l < r) {
            int m = l + (r - l >> 1);
            if (a / m <= b) r = m;
            else l = m + 1;
        }
        vmn = max(vmn, l);
        l = 1, r = 2e9;
        while (l < r) {
            int m = l + (r - l + 1 >> 1);
            if (a / m >= b) l = m;
            else r = m - 1;
        }
        vmx = min(vmx, r);
    }
    printf("%d %d\n", vmn, vmx);
    
    return 0;
}

方法二：数学

思路

$V_i$ 的上界和下界也可以通过公式直接算出来。

$$\begin{aligned} \lfloor \frac{A_i}{V_i} \rfloor = B_i &\Longrightarrow \frac{A_i}{V_i} \in [B_i, B_i + 1) \\ &\Longrightarrow B_i \le \frac{A_i}{V_i} < B_i + 1 \\ &\Longrightarrow \frac{A_i}{B_i + 1} < V_i \le \frac{A_i}{B_i} \\ &\Longrightarrow V_{i_{max}} = \lfloor \frac{A_i}{B_i} \rfloor, \enspace V_{i_{min}} = \begin{cases} \frac{A_i}{B_i + 1} + 1 & \frac{A_i}{B_i + 1} \in \mathbb{Z} \\ \lceil \frac{A_i}{B_i + 1} \rceil & \frac{A_i}{B_i + 1} \notin \mathbb{Z} \end{cases} \\ &\Longrightarrow V_{i_{max}} = \lfloor \frac{A_i}{B_i} \rfloor, \enspace V_{i_{min}} = \lfloor \frac{A_i}{B_i + 1} \rfloor + 1 \end{aligned}$$

代码

#include <iostream>

using namespace std;

int n, a, b;

int main() {
    scanf("%d", &n);
    int vmn = 1, vmx = 2e9;
    while (n--) {
        scanf("%d%d", &a, &b);
        vmn = max(vmn, a / (b + 1) + 1);
        vmx = min(vmx, a / b);
    }
    printf("%d %d\n", vmn, vmx);
    
    return 0;
}