【蓝桥杯集训·每日一题2025】 AcWing 4905. 面包店 python

AcWing 4905. 面包店

Week 4
3月14日

题目描述

贝茜开了一家面包店。

贝茜的面包店中只有一个烤箱，该烤箱制作一块饼干需要花费的时间为 $t_C$，制作一块松饼需要花费的时间为 $t_M$。

烤箱每次只能制作一个糕点，也就是说制作 $A$ 块饼干和 $B$ 块松饼需要花费的时间为 $A\times t_C+B\times t_M$。

有 $N$ 个客人来光顾贝茜的生意，编号 $1\sim N$。

客人是一个接着一个来的，并且第 $i+1$ 个客人一定会在第 $i$ 个客人走后才会来。

第 $i$ 个客人想要 $a_i$ 块饼干和 $b_i$ 块松饼。

为了保证售出糕点足够新鲜，贝茜一定会在客人下单后才开始现场制作其所需要的全部糕点。

每个客人的耐心都是有限的，对于第 $i$ 个客人，如果贝茜制作其所需全部糕点花费的总时间超过 $c_i$，那么它就会生气离开。

贝茜不希望得罪任何客人，在第 $1$ 个客人到来之前，它可以选择对它的烤箱进行升级。

烤箱每升一级，可以进行如下选择：要么使得生产一块饼干所需的时间减少 $1$，要么使得生产一块松饼所需的时间减少 $1$。

注意：不论如何升级烤箱，生产饼干或松饼的时间至少为 $1$。

请你计算，为了让所有客人都能满意，至少需要升多少级烤箱。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行是空行。

第二行包含三个整数 $N,t_C,t_M$。

接下来 $N$ 行，每行包含三个整数 $a_i,b_i,c_i$。

输出格式

每组数据输出一行结果，一个整数，表示烤箱需要的最小升级数量。

数据范围

$1\le T\le 100$,
$1\le N\le 100$,
$1\le t_C,t_M\le 10^9$,
$1\le a_i,b_i\le 10^9$,
$a_i+b_i\le c_i\le 2\times 10^{18}$

输入样例：

2

3 7 9
4 3 18
2 4 19
1 1 6

5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

输出样例：

11
6

样例解释

对于第一组数据，贝茜可以对烤箱进行 $11$ 次升级，其中 $4$ 次减少饼干制作时间，$7$ 次减少松饼制作时间，升级过后制作一块饼干的时间为 $3$，制作一块松饼的时间为 $2$。

这样的话，完成第 $1$ 个客人的订单需要花费的总时间为 $18$，完成第 $2$ 个客人的订单需要花费的总时间为 $14$，完成第 $3$ 个客人的订单需要花费的总时间为 $5$，所有人都可以满意离开。

对于第二组数据，贝茜可以对烤箱进行 $6$ 次升级，全部用于减少饼干制作时间。

二分答案 + 不等式求交集

AC_code

from math import ceil, floor  
  
def check(mid):  
    l, r = max(0, mid - t2 + 1), min(t1 - 1, mid)  
    for i in range(n):  
        a, b, c = arr[i]  
        tmp = c - a * t1 - b * t2 + b * mid  
        if a == b:  
            if tmp < 0:  
                return 0  
        elif a < b:  
            r = min(r, floor(tmp / (b - a)))  
        else:  
            l = max(l, ceil(tmp / (b - a)))  
    return l <= r  
  
t = int(input())  
for _ in range(t):  
    input()  
    n, t1, t2 = map(int, input().split())  
    arr = [list(map(int, input().split())) for _ in range(n)]  
    l, r = 0, t1 + t2 - 2  
    while l <= r:  
        mid = (l + r) // 2  
        if check(mid):  
            ans = mid  
            r = mid - 1  
        else:  
            l = mid + 1  
    print(ans)

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢