自动搬运

查看原文

来自洛谷，原作者为

	Ceyase 当羽毛飞向天际。

搬运于2025-08-24 23:13:20，当前版本为作者最后更新于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()