洛谷 P12167 [蓝桥杯 2025 省 C/Python A] 倒水–二分答案法

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

题目描述

小蓝有 $n$ 个装了水的瓶子，从左到右摆放，第 $i$ 个瓶子里装有 $a_i$ 单位的水。为了美观，小蓝将水循环染成了 $k$ 种颜色，也就是说，第 $i$ 个瓶子和第 $i+k$ 个瓶子里的水的颜色相同。

小蓝发现有的瓶子里的水太少了，因此他规定如果第 $i$ 个瓶子和第 $j$ 个瓶子中的水颜色相同并且满足 $i<j$，即可将任意整数单位的水从第 $i$ 个水瓶倒出，倒入第 $j$ 个水瓶中。小蓝想知道任意次操作后所有瓶子中的水的最小值 min⁡{ai}\min\{a_i\}min{ai​} 最大可以是多少？

输入格式

输入的第一行包含两个正整数 $n,k$，用一个空格分隔。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

7 3
8 5 5 2 2 3 4

输出 #1

3

说明/提示

样例说明

其中一种方案：

• $a_1$ 往 $a_4$ 倒入 $3$ 单位；
• $a_2$ 往 $a_5$ 倒入 $2$ 单位；
• $a_3$ 往 $a_6$ 倒入 $1$ 单位；
  最终每个瓶子里的水：$5,3,4,5,4,4,4$，最小值为 $3$。

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$1\le n,a_i\le 100$；
• 对于所有评测用例，$1\le n,a_i\le 100000$，$1\le k\le n$。
  这是一道经典的“最大化最小值”问题。在算法竞赛中，看到“求最小值的最大可能是多少”或者“最大值的最小可能是多少”这类字眼，十有八九需要使用“二分答案”算法来求解。

一、核心思路

1.独立的分组

题目规定，第 i 个瓶子只能和第 i + k 个瓶子颜色相同，且水只能在同色瓶子间转移。这意味着，所有瓶子被完美地切分成了 k 个互相不干扰的“独立小组”。例如，当 k=3 时：
第 1 组：包含索引为 0, 3, 6, 9… 的瓶子
第 2 组：包含索引为 1, 4, 7, 10… 的瓶子
第 3 组：包含索引为 2, 5, 8, 11… 的瓶子
水绝对不可能跨越小组流动，因此我们可以对每个小组单独处理。

2.单向流动（从左到右）

题目明确规定，水只能从第 i 个瓶子倒入第 j 个瓶子，且必须满足 i < j。也就是说，水在同组内只能从左往右流，不能倒流。这就得出一个关键结论：如果要让某个瓶子的水量达标，它只能向它左边的瓶子“借水”。如果在从左到右遍历的过程中，前面累积的多余水量不够填补当前瓶子的缺口，那么这个目标就绝对无法达成。

3.二分答案写法

与其去直接计算最大的最小值是多少，不如我们“猜”一个目标值 mid，然后去验证：

• “有没有可能让所有瓶子的水量都至少达到 mid？
• ”如果可以达到，说明我们可能猜小了，尝试去猜一个更大的值。
• 如果达不到（某个瓶子怎么借水都不够 mid），说明猜大了，缩小范围猜个更小的值。

二、Python代码实现

def check(mid, groups):
		"""
		验证是否有可能通过倒水，让所有瓶子的水量都 >= target_water
		"""
    # 遍历每一个独立的分组
    for group in groups:
    		 # reserve 记录当前组从左到右累积的“多余水量”
        reverse = 0
        for water in group:
        		# 加上当前瓶子多出来的水（如果是缺水，水就是负数，相当于消耗 reserve）
            reverse += (water - mid)
            # 如果多余的水量变成负数，说明前面的水全倒过来也不够填补当前的缺口
            # 因为水不能从右边倒流回来，所以当前 target_water 绝对无法实现
            if reverse < 0:
                return False
    # 如果所有组都能通过考验，说明这个 target_water 是可行的
    return True


def solve():
    data1 = input().split()
    n = int(data1[0])
    k = int(data1[1])

    data2 = input().split()
    # 提取初始水量的数组
    num = [int(x) for x in data2]
		
	# 将瓶子按颜色分入 k 个独立的小组
    # groups 是一个包含 k 个列表的列表
    groups = [[] for _ in range(k)]

    for i in range(n):
        groups[i % k].append(num[i])
		
	# 二分答案求最大化最小值
    left = 0
    right = max(num)   # 水量再怎么集中，平均下来的最小值也不可能超过初始水量的最大值
    ans = 0

    while left <= right:
        mid = (left + right) // 2

		# 如果当前目标水量 mid 是可行的
        if check(mid, groups):
            ans = mid    # 先把这个可行的答案记录下来
            left = mid + 1    # 然后贪心地去右半区间尝试更大的可能
        else:   # 如果不可行，说明猜大了，去左半区间寻找
            right = mid - 1
    print(ans)


if __name__ == '__main__':
    solve()

三、复杂度分析

• 时间复杂度：$O(N\log M)$。将瓶子分组的时间是 $O(N)$。二分查找的最大范围是水量的最大值 $100000$，最多二分约 $17$ 次（$2^{17}>100000$）。每次 check 需要遍历全部 $N$ 个瓶子，耗时 $O(N)$。总体数据量 $17\times 10^5\approx 1.7\times 10^6$ 次计算，在 Python 中大概只需要不到 0.1 秒即可跑完，非常安全。
• 空间复杂度：$O(N)$。使用了一个二维数组 groups 来存储重新分组后的瓶子，占用的空间等同于输入数据的规模。

四、 “二分答案”算法总结

“二分答案”的模板非常固定，难点通常在与怎么写check函数。使用该方法的题目通常有以下特征：

1.标志性的“题眼”

• 最大值最小化：例如“求所有分组中，和最大的那一组，其值最小是多少？”
• 最小值最大化：就像刚才那道倒水题，“求所有瓶子水量的最小值，最大可以是多少？”
• 求最大的满足条件的值：例如“求最多能切出多少根长度相等的木材？”
• 求最小的满足条件的值：例如“求最少需要花费多少时间才能完成所有任务？”

2.隐藏的逻辑特征

• 答案具有单调性
  这是最根本的前提。假设你要找的答案是 $X$。
  如果猜的答案比 $X$ 小，那么任务一定能完成（或者一定不能）；
  如果猜的答案比 $X$ 大，那么任务一定不能完成（或者一定能）。
• “正向求解”极难，但“判定结果”极易
  -有些题目你顺着推导完全找不到公式，但是如果我硬塞给你一个结果（也就是二分猜出来的 mid），让你去验证“这个结果能不能达成”，往往只需要一个简单的 for 循环加上一点贪心策略就能搞定。这就是为什么我们会专门写一个 check(mid) 函数。

3.代码骨架

1.定边界：找到答案可能的最小值 left 和最大值 right。
2.写二分：while left <= right，计算中间值 mid = (left + right) // 2。
3.写验证：核心心血全部倾注在 check(mid) 函数上，用贪心或模拟去验证 mid 是否可行。
4.缩区间：根据 check 的结果，移动 left 或 right，并记录正确的答案。