倒水

蓝桥杯-倒水

二分答案

n, k = map(int, input().split())
a = list(map(int, input().split()))

def check(mid):
    b = a[:]
    # 从前往后，贪心地倒水
    for i in range(n - k):
        if b[i] > mid:
            # 把多余的倒给后面同色的瓶子
            b[i + k] += b[i] - mid
            b[i] = mid
    # 检查所有瓶子是否都 >= mid
    return min(b) < mid

lo, hi = 1, max(a) + 1
while lo < hi:
    i = (lo + hi) >> 1
    if check(i):
        hi = i
    else:
        lo = i + 1

print(lo - 1)

这是一个二分答案题目，可使用二分答案模板来进行解答（蓝桥杯Python目前不支持往bisect添加check函数检查）

# lo: 左边界 hi: 右边界
# 等价于 bisect_right 查找右边第一个大于target的下标（左闭右开）
while lo < hi:
    i = (lo + hi) >> 1
    if check(i):
        hi = i
    else:
        lo = i + 1