侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-04-12 / 0 评论 / 0 点赞 / 65 阅读 / 1,448 字
温馨提示:
本文最后更新于 2023-04-12,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

4956. 冶炼金属 - AcWing题库

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


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

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

现在给出了 NN 条冶炼记录,每条记录中包含两个整数 AABB ,这表示本次投入了 AA 个普通金属 OO ,最终冶炼出了 BB 个特殊金属 XX

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

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

输入格式

第一行一个整数 NN ,表示冶炼记录的数目。

接下来输入 NN 行,每行两个整数 ABA、B ,含义如题目所述。

输出格式

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

数据范围

对于 30%30\% 的评测用例, 1N1021 ≤ N ≤ 10^2
对于 60%60\% 的评测用例, 1N1031 ≤ N ≤ 10^3
对于 100%100\% 的评测用例, 1N1041 ≤ N ≤ 10^41BA1091 ≤ B ≤ A ≤ 10^9

输入样例:

3
75 3
53 2
59 2

输出样例:

20 25

样例解释

V=20V = 20 时,有: 7520=3⌊\frac{75}{20} ⌋ = 35320=2⌊\frac{53}{20} ⌋ = 25920=2⌊\frac{59}{20} ⌋ = 2 ,可以看到符合所有冶炼记录。

V=25V = 25 时,有: 7525=3⌊\frac{75}{25} ⌋ = 35325=2⌊\frac{53}{25} ⌋ = 25925=2⌊\frac{59}{25} ⌋ = 2 ,可以看到符合所有冶炼记录。

且再也找不到比 2020 更小或者比 2525 更大的符合条件的 VV 值了。

解题

方法一:二分查找

思路

由题意可知,我们需要找出 VminV_{min}VmaxV_{max} ,使得 AiV=Bi\lfloor \frac{A_i}{V} \rfloor = B_i (其中 i=1N,V[Vmin,Vmax]i = 1\dots{N}, \enspace V \in[V_{min}, V_{max}] )。

由于每条冶炼记录都是独立的,要使所有冶炼记录都成立, VV 的范围就应是所有 ViV_i 的交集,也就是说: Vmin=max(V1min,V2min,,VNmin),Vmax=min(V1max,V2max,,VNmax)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}})

对于第 ii 条冶炼记录,AiVi\frac{A_i}{V_i} 是单调的( Vi,AiViV_i \uparrow, \frac{A_i}{V_i} \downarrow ),所以 ViV_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;
}

方法二:数学

思路

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

AiVi=BiAiVi[Bi,Bi+1)BiAiVi<Bi+1AiBi+1<ViAiBiVimax=AiBi,Vimin={AiBi+1+1AiBi+1ZAiBi+1AiBi+1ZVimax=AiBi,Vimin=AiBi+1+1\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;
}
0

评论区