P9240 [蓝桥杯 2023 省 B] 冶炼金属 Python

[蓝桥杯 2023 省 B] 冶炼金属

题目描述

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V V V V V V 是一个正整数,这意味着消耗 V V V 个普通金属 O 恰好可以冶炼出一个特殊金属 X,当普通金属 O 的数目不足 V V V 时,无法继续冶炼。

现在给出了 N N N 条冶炼记录,每条记录中包含两个整数 A A A B B B,这表示本次投入了 A A A 个普通金属 O,最终冶炼出了 B B B 个特殊金属 X。每条记录都是独立的,这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

3
75 3
53 2
59 2

样例输出 #1

20 25

提示

【样例说明】

V = 20 V=20 V=20 时,有: ⌊ 75 20 ⌋ = 3 , ⌊ 53 20 ⌋ = 2 , ⌊ 59 20 ⌋ = 2 \left\lfloor\frac{75}{20}\right\rfloor=3,\left\lfloor\frac{53}{20}\right\rfloor=2,\left\lfloor\frac{59}{20}\right\rfloor=2 2075=3,2053=2,2059=2,可以看到符合所有冶炼记录。

V = 25 V=25 V=25 时,有: ⌊ 75 25 ⌋ = 3 , ⌊ 53 25 ⌋ = 2 , ⌊ 59 25 ⌋ = 2 \left\lfloor\frac{75}{25}\right\rfloor=3,\left\lfloor\frac{53}{25}\right\rfloor=2,\left\lfloor\frac{59}{25}\right\rfloor=2 2575=3,2553=2,2559=2,可以看到符合所有冶炼记录。

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

【评测用例规模与约定】

对于 30 % 30 \% 30% 的评测用例, 1 ≤ N ≤ 1 0 2 1 \leq N \leq 10^{2} 1N102

对于 60 % 60 \% 60% 的评测用例, 1 ≤ N ≤ 1 0 3 1 \leq N \leq 10^{3} 1N103

对于 100 % 100 \% 100% 的评测用例, 1 ≤ N ≤ 1 0 4 1 \leq N \leq 10^{4} 1N104 1 ≤ B ≤ A ≤ 1 0 9 1 \leq B \leq A \leq 10^{9} 1BA109

蓝桥杯 2023 省赛 B 组 C 题。

思路:
数学问题 先分析一组数据,这一组数据中,应该有一个最大值,一个最小值
最开始的想法是挨个遍历,找到这些值,但提交之后发现超时
一个测试点都没有通过,那接下来的难点就是怎么确定最值的问题了。
拿75 和 3举例 ,他的最大值应该是 25 因为如果超了25 就不能是三个了,如此当这些金属能恰好能做成4个的时候,也是临界值 75/4=18.75
即:V=18 + 1( a//(b+1) + 1)的时候 为最小值
一组数据分析完成之后,再继续分析,我们可以发现,满足需求的 是要求在最小值中找到最大值,最大值中找到最小值,该部分是解题的关键

超时做法

n = int(input())
min_l=[]
max_l=[]
for i in range(n):
    s = []
    a,b = map(int,input().split())
    for i in range(1,a+1):
        if a//i==b:
            s.append(i)

    min_l.append(s[0])
    max_l.append(s[-1])

print(min_l[-1],max_l[0])

正确答案

import math

n = int(input())
min_v=0
max_v=math.inf
for i in range(n):
    s = []
    a,b = map(int,input().split())
    min_v =max(min_v, a//(b+1) + 1)#最小值里找最大
    max_v = min(max_v,a//b)#最大值里找最小
print(min_v,max_v)
上一篇:【华为OD机试】高效货运【C卷|200分】


下一篇:Github 2024-03-19 Python开源项目日报 Top10