[蓝桥杯 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} 1≤N≤102。
对于 60 % 60 \% 60% 的评测用例, 1 ≤ N ≤ 1 0 3 1 \leq N \leq 10^{3} 1≤N≤103。
对于 100 % 100 \% 100% 的评测用例, 1 ≤ N ≤ 1 0 4 1 \leq N \leq 10^{4} 1≤N≤104, 1 ≤ B ≤ A ≤ 1 0 9 1 \leq B \leq A \leq 10^{9} 1≤B≤A≤109。
蓝桥杯 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)