题解：P12167 [蓝桥杯 2025 省 C/Python A] 倒水

Ceyase · 2025-08-11 18:04:16 · 题解

P12167

由于是最小值最大化的题目，我们当然会想到二分答案。

对于目标最小值 x，我们可以检查是否所有瓶子都至少能装 x 个单位的水。

先将 n 个瓶子 a_i 划分为 k 组，第 i 组 G_i=\{a_j \mid j \bmod k = i\}(0 \leq i < k)。

由于在每组中，水只能从左往右倒，所以前面的瓶子可以支援后面的，但后面的不能支援前面的。

因此我们需要验证每个组中，从左到右的累积水量是否在每个步骤都能满足 x。具体来说，对于组中的每个瓶子，从组开始到该瓶子的水量之和必须至少是 x 乘以该组已处理的瓶子数量。

假如前 i+1 个瓶子的总水量小于 (i+1)×x，那么前 i+1 个瓶子中必然会有一个瓶子的水量小于 x，此时 x 当然就不是最小值了。

代码实现

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    a = list(map(int, data[2:2+n]))
    total = sum(a)
    groups = [[] for _ in range(k)]
    for i in range(n):
        groups[i % k].append(a[i])
    l, r = 0, total // n
    def check(x):
        for group in groups:
            s = 0
            for num in group:
                s += num - x
                if s < 0:
                    return False
        return True
    while l <= r:
        mid = (l + r) // 2
        if check(mid):
            l = mid + 1
        else:
            r = mid - 1
    print(r)
if __name__ == "__main__":
    main()