当前位置：首页 > news >正文

瓶子倒水二分法：最大化最小值

news 2026/4/20 1:49:59

一、题目描述（核心背景与要求）

1. 题目背景

小蓝有n 个装水的瓶子，从左到右依次摆放，第 i 个瓶子装有 aᵢ 单位的水；为了美观，瓶子按 k 种颜色循环染色（第 i 个与第 i+k 个颜色相同）。

2. 操作规则

同颜色组内，若满足i < j（左瓶下标小于右瓶），可将任意整数单位的水从 i 倒入 j；
操作次数不限，水的总量保持不变（水守恒）；
不同颜色组的瓶子，无法互相倒水（组间独立）。

3. 核心问题

二、题目拆解（规则+目标+核心限制）

1. 核心规则拆解——分组逻辑

由“k种颜色循环染色”可推出：瓶子按「下标对k取余」分成 k 个独立组，分组方式如下：

第 0 组：下标为 0, k, 2k, 3k, ...（对应题目第 1、k+1、2k+1 个瓶子）
第 1 组：下标为 1, k+1, 2k+1, ...
... ...
第 k-1 组：下标为 k-1, 2k-1, 3k-1, ...

重点标注：组间完全独立，水不能跨组流动，因此可对每个组单独分析，再整合结果。

2. 倒水规则的核心限制

只能左倒右：右瓶可接收左瓶的水，左瓶无法接收右瓶的水；
左瓶水量上限：左瓶的最终水量 ≤ 初始水量（无法从右侧获取水，最多保留自身水量）；
右瓶水量无上限：右瓶可接收同组所有左侧瓶子的水，只要组内总水量足够。

3. 目标拆解

题目目标是「最大化所有瓶子的最小值」，这类问题是算法中经典的「最大化最小值题型」，此类题型有固定的最优解题思路——二分答案法。

三、解题思路推导（从题型到方法）

1. 为什么优先选择「二分答案法」？

「最大化最小值」题型的核心特性：答案具有单调性，具体表现为：

若某个值 x 可行（能让所有瓶子水量 ≥ x），则所有小于 x 的值都一定可行；
若某个值 x 不可行（无法让所有瓶子水量 ≥ x），则所有大于 x 的值都一定不可行。

这种“可行/不可行”的分界特性，恰好适配二分法的核心逻辑——通过不断缩小区间，找到最大的可行值。

2. 其他方法对比（为什么不选）

方法	优势	劣势	是否选用
暴力枚举	逻辑简单	x 最大可达 1e12，超时严重	否
贪心算法	效率较高	需复杂分配逻辑，易出错	否
二分答案法	逻辑清晰、效率高（仅需40次左右判断）	需设计判断函数	是（最优解）

3. 二分答案法的整体框架

核心框架（必记）：

确定二分边界：左边界 l=0（水量最小为0），右边界 r=总水量/n（理论最大均衡值）；
取中间值 mid = (l + r) / 2（避免溢出用 l + (r-l)/2）；
判断 mid 是否可行（设计 check(mid) 函数）；
可行则尝试更大值（l=mid+1），不可行则尝试更小值（r=mid-1）；
循环结束，最大可行值即为答案。

四、核心函数设计（check(x)详解）

1. check(x) 函数的作用

给定一个目标值 x，判断：经过任意次合法操作后，能否让所有瓶子的水量都 ≥ x。

由于组间独立，只需判断每个组是否满足条件，所有组满足则 x 可行，否则不可行。

2. 单个组的可行条件（核心重点）

设某组的总水量为 sum，瓶子数量为 cnt，要让组内所有瓶子水量 ≥ x，需同时满足两个条件：

条件1：组内总水量足够（水守恒）

sum ≥ x * cnt

重点标注：若组内总水量不足以给每个瓶子分配 x 单位水，无论怎么倒水，都无法让所有瓶子达标，直接判定不可行。

条件2：组内左侧瓶子初始水量足够

从左到右遍历组内瓶子，直到遇到第一个初始水量 < x 的瓶子为止：

该瓶子左侧的所有瓶子，初始水量必须 ≥ x；
原因：左侧瓶子无法从右侧获取水，初始水量 < x 则永远无法达到 x；
右侧瓶子可通过左侧倒水补足 x，无需再检查。

3. check(x) 函数逻辑梳理

遍历每一个颜色组；
对每个组，先判断条件1（sum ≥ x*cnt），不满足则返回 false；
再判断条件2（左侧瓶子初始水量 ≥ x），不满足则返回 false；
所有组均满足条件，返回 true。

五、整体流程与样例验证

1. 整体解题流程（步骤化）

分组计算：遍历 k 个组，计算每个组的总水量 sum 和瓶子数量 cnt；
初始化二分边界：l=0，r=所有瓶子总水量 / n；
二分迭代：计算 mid，调用 check(mid)，调整 l 和 r，记录最大可行值；
输出最大可行值，即为最终答案。

2. 样例验证（直观理解）

步骤1：分组计算

组0：[8, 2, 4] → sum=14，cnt=3
组1：[5, 2] → sum=7，cnt=2
组2：[5, 3] → sum=8，cnt=2

总水量=29，右边界 r=29/7≈4。

步骤2：二分验证

试 mid=3：
- 组0：14 ≥ 3*3=9（条件1满足）；左侧8≥3，遇到2<3停止（条件2满足）；
- 组1：7 ≥ 3*2=6（条件1满足）；左侧5≥3，遇到2<3停止（条件2满足）；
- 组2：8 ≥ 3*2=6（条件1满足）；5≥3、3≥3（条件2满足）；
- → mid=3 可行，尝试更大值（l=4）。
试 mid=4：
- 组1：7 ≥ 4*2=8（条件1不满足）；
- → mid=4 不可行，尝试更小值（r=3）。

步骤3：最终答案

循环结束，最大可行值为 3，即答案为 3。

六、完整代码实现（可直接运行）

重点标注：代码采用函数式结构，分工清晰；使用long long 避免溢出，适配题目数据范围。

#include <stdio.h>
#include <stdbool.h>

// 数组最大长度（适配 n≤1e6 的题目要求）
#define MAXN 1000005

// 全局变量（简化参数传递，新手易理解）
long long a[MAXN];// 存储每个瓶子的初始水量
long long sum[MAXN];// 存储每个组的总水量
int cnt[MAXN];// 存储每个组的瓶子数量
int n, k;// n：瓶子总数，k：颜色种类数

// 核心判断函数：判断能否让所有瓶子水量 ≥ x
bool check(long long x) {
// 遍历每一个颜色组
for (int c = 0; c < k; c++) {
// 条件1：组总水量足够
if (sum[c] < x * cnt[c]) {
return false;
}
// 条件2：左侧瓶子初始水量足够
for (int i = c; i < n; i += k) {
if (a[i] < x) {
break;// 遇到第一个<x的，后面无需检查
}
}
}
// 所有组都满足条件，x可行
return true;
}

// 主逻辑函数：二分查找最大可行值
long long solve() {
// 1. 分组计算 sum（总水量）和 cnt（瓶子数量）
for (int c = 0; c < k; c++) {
sum[c] = 0;
cnt[c] = 0;
// 遍历当前组的所有瓶子（下标 c, c+k, c+2k...）
for (int i = c; i < n; i += k) {
sum[c] += a[i];
cnt[c]++;
}
}

// 2. 初始化二分边界
long long l = 0;// 左边界：最小可能值
long long r = 0;// 右边界：理论最大可能值
// 计算总水量，右边界设为总水量/n（所有瓶子均衡时的最小值）
for (int i = 0; i < n; i++) {
r += a[i];
}
r /= n;

long long ans = 0;// 存储最终答案
// 3. 二分迭代查找
while (l <= r) {
// 计算中间值，避免 (l+r)/2 溢出
long long mid = l + (r - l) / 2;
if (check(mid)) {
ans = mid;// 记录可行值
l = mid + 1;// 尝试更大的值
} else {
r = mid - 1;// 尝试更小的值
}
}
return ans;
}

// 主函数：负责输入输出，调用核心逻辑
int main() {
// 输入 n 和 k
scanf("%d %d", &n, &k);
// 输入 n 个瓶子的初始水量
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
// 调用 solve() 计算答案，输出结果
printf("%lld\n", solve());
return 0;
}