问题分析

小塔有三种砖块：红砖、蓝砖和绿砖，分别有 a、b、c 个。我们可以进行合成操作，合成规则是：

• 每 x 个红砖可以合成 1 个蓝砖。
• 每 y 个蓝砖可以合成 1 个绿砖。

我们需要计算小塔最多能够收集到多少套砖块。一套砖块需要一个红砖、一个蓝砖和一个绿砖。

思考合成与二分答案

本题可以使用 二分答案 来解决问题。那我们自然要问一个问题：$min(红砖,蓝砖,绿砖)$ 这个东西是否有单调性？

假设有如下情况：

• 红砖：8
• 蓝砖：3
• 绿砖：1
• 每 4 个红砖可以合成 1 个蓝砖
• 每 2 个蓝砖可以合成 1 个绿砖

1.假设我们要使用合成操作让$min(红砖,蓝砖,绿砖)= 0$ ， 这是很容易做到。我们可以把红砖全部给合成给蓝砖。

情况从8 3 1变为0 5 1 , min(0,5,1)=0

2.试着让它变大 ， 比如:$min(红砖,蓝砖,绿砖) = 2$ 。 这比刚刚难做到了。因为我们还要至少留两块给红砖

情况从8 3 1变为4 4 1 -> 4 2 2 。

3.继续试着让它变更大，比如$min(红砖,蓝砖,绿砖) = 8$ 。 这更难了。这样我们无法操作红砖，而蓝砖和红砖数量都少于10。

体会上述过程，我们发现答案越大越难达成，即具有单调性，我们要求的就是这个刚好能达成的临界值。所以我们可以通过二分查找来确定 mid，即最多可以收集多少套砖块。从红砖开始操作，每次将多于mid的部分都传递到蓝砖。然后蓝砖多余mid的部分（如果有）传递给绿砖，最后判断$min(红砖,蓝砖,绿砖) \geq mid$ 是否成立。成立就l = mid + 1 , 否则r = mid - 1

二分查找的核心步骤

1. 初始区间：我们定义一个区间 [l, r]，其中 l 是最小的套数（即 0），r 是最大可能的套数（即最大的砖块数量）。

2. 二分查找：在每次查找时，计算当前区间的中点 mid，然后判断是否能够通过合成操作使得红砖、蓝砖和绿砖的数量满足 mid 套的需求。

3. 合成判断：如果当前的 mid 套数可以通过合成满足要求，那么就尝试更大的 mid，否则就减少 mid。

代码实现

def check(a, b, c, mid):
    a1, b1, c1 = a, b, c

    # 尝试从红砖合成蓝砖
    if a1 > mid:
        f = (a1 - mid) // x  # 计算多余的红砖能合成多少蓝砖
        a1 -= x * f  # 消耗掉这些红砖
        b1 += f  # 增加蓝砖的数量

    # 尝试从蓝砖合成绿砖
    if b1 > mid:
        f = (b1 - mid) // y  # 计算多余的蓝砖能合成多少绿砖
        b1 -= y * f  # 消耗掉这些蓝砖
        c1 += f  # 增加绿砖的数量

    return a1 >= mid and b1 >= mid and c1 >= mid

# 读取测试数据的组数
T = int(input())

# 遍历每一组数据
for _ in range(T):
    # 读取每组数据
    a, b, c, x, y = map(int, input().split())

    # 二分查找的左边界和右边界
    l = 0
    r = 10**9

    # 二分查找
    while l < r:
        mid = (l + r + 1) // 2  # 尝试获取的中间套数
        
        # 如果经过合成后，红砖、蓝砖、绿砖都能满足mid套，则可以尝试更大的mid
        if check(a, b, c, mid):
            l = mid
        else:
            r = mid - 1  # 否则尝试更小的mid

    # 输出结果，即最多可以收集到的砖块套数
    print(l)

本题为2024年9月14日美团机考原题

美团机考的介绍点击这里

题目内容

小塔有$a$个红砖、$b$个蓝砖和$c$个绿砖。每$x$个红砖可以合成$1$个蓝砖，每$y$个蓝砖可以合成$1$个绿砖。砖块只能正向合成，不能反向分解。 一套砖块包含$1$个红砖、$1$个蓝砖和$1$个绿砖。请计算小塔最多可以收集多少套砖块。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤10^5)$代表数据组数，每组测试数据描述如下: 在一行上输入五个整数$a,b,c,x,y(0≤a,b,c≤10^9,1≤x,y≤10^9)$，分别表示红砖、蓝砖、绿砖的数量及合成的比例。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表小塔最多可以收集到的砖块套数。

样例1

输入

2
1 2 3 4 2
10 2 1 4 2

输出

1
2

说明

对于第一组测试数据，无法进行合成转换，故只能收集初始的一套。 对于第二组测试数据，可以把$8$个红砖转为$2$个蓝砖、把$2$个蓝砖转化为$1$个绿砖。这样每种的砖块数量分别为$[2, 2,2]$，刚好凑成$2$套。