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

一、题目描述核心背景与要求1. 题目背景小蓝有n 个装水的瓶子从左到右依次摆放第 i 个瓶子装有 aᵢ 单位的水为了美观瓶子按 k 种颜色循环染色第 i 个与第 ik 个颜色相同。2. 操作规则同颜色组内若满足i j左瓶下标小于右瓶可将任意整数单位的水从 i 倒入 j操作次数不限水的总量保持不变水守恒不同颜色组的瓶子无法互相倒水组间独立。3. 核心问题二、题目拆解规则目标核心限制1. 核心规则拆解——分组逻辑由“k种颜色循环染色”可推出瓶子按「下标对k取余」分成 k 个独立组分组方式如下第 0 组下标为 0, k, 2k, 3k, ...对应题目第 1、k1、2k1 个瓶子第 1 组下标为 1, k1, 2k1, ...... ...第 k-1 组下标为 k-1, 2k-1, 3k-1, ...重点标注组间完全独立水不能跨组流动因此可对每个组单独分析再整合结果。2. 倒水规则的核心限制只能左倒右右瓶可接收左瓶的水左瓶无法接收右瓶的水左瓶水量上限左瓶的最终水量 ≤ 初始水量无法从右侧获取水最多保留自身水量右瓶水量无上限右瓶可接收同组所有左侧瓶子的水只要组内总水量足够。3. 目标拆解题目目标是「最大化所有瓶子的最小值」这类问题是算法中经典的「最大化最小值题型」此类题型有固定的最优解题思路——二分答案法。三、解题思路推导从题型到方法1. 为什么优先选择「二分答案法」「最大化最小值」题型的核心特性答案具有单调性具体表现为若某个值 x 可行能让所有瓶子水量 ≥ x则所有小于 x 的值都一定可行若某个值 x 不可行无法让所有瓶子水量 ≥ x则所有大于 x 的值都一定不可行。这种“可行/不可行”的分界特性恰好适配二分法的核心逻辑——通过不断缩小区间找到最大的可行值。2. 其他方法对比为什么不选方法优势劣势是否选用暴力枚举逻辑简单x 最大可达 1e12超时严重否贪心算法效率较高需复杂分配逻辑易出错否二分答案法逻辑清晰、效率高仅需40次左右判断需设计判断函数是最优解3. 二分答案法的整体框架核心框架必记确定二分边界左边界 l0水量最小为0右边界 r总水量/n理论最大均衡值取中间值 mid (l r) / 2避免溢出用 l (r-l)/2判断 mid 是否可行设计 check(mid) 函数可行则尝试更大值lmid1不可行则尝试更小值rmid-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) 函数逻辑梳理遍历每一个颜色组对每个组先判断条件1sum ≥ x*cnt不满足则返回 false再判断条件2左侧瓶子初始水量 ≥ x不满足则返回 false所有组均满足条件返回 true。五、整体流程与样例验证1. 整体解题流程步骤化分组计算遍历 k 个组计算每个组的总水量 sum 和瓶子数量 cnt初始化二分边界l0r所有瓶子总水量 / n二分迭代计算 mid调用 check(mid)调整 l 和 r记录最大可行值输出最大可行值即为最终答案。2. 样例验证直观理解步骤1分组计算组0[8, 2, 4] → sum14cnt3组1[5, 2] → sum7cnt2组2[5, 3] → sum8cnt2总水量29右边界 r29/7≈4。步骤2二分验证试 mid3组014 ≥ 3*39条件1满足左侧8≥3遇到23停止条件2满足组17 ≥ 3*26条件1满足左侧5≥3遇到23停止条件2满足组28 ≥ 3*26条件1满足5≥3、3≥3条件2满足→ mid3 可行尝试更大值l4。试 mid4组17 ≥ 4*28条件1不满足→ mid4 不可行尝试更小值r3。步骤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颜色种类数// 核心判断函数判断能否让所有瓶子水量 ≥ xbool 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, ck, c2k...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) {// 计算中间值避免 (lr)/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 和 kscanf(%d %d, n, k);// 输入 n 个瓶子的初始水量for (int i 0; i n; i) {scanf(%lld, a[i]);}// 调用 solve() 计算答案输出结果printf(%lld\n, solve());return 0;}七、思路总结与同类题技巧1. 完整思路总结必记核心思考链读题拆规则循环染色→k个独立组只能左倒右→左瓶水量有上限识别题型最大化最小值→优先用二分答案法设计核心函数check(x) 需满足「总水量足够左侧初始水量足够」落地代码分组求和→二分迭代→输出答案。2. 同类题解题技巧看到「最大化最小值」「最小化最大值」直接优先考虑二分答案法二分法的核心是「判断函数」需结合题目规则设计可行条件涉及大数值如总水量≥1e12必须用 long long 避免溢出分组问题优先考虑「组间独立」单独分析每组再整合结果。3. 常见易错点提醒忘记左瓶水量上限忽略 check(x) 的条件2用 int 存储总水量导致溢出二分边界设置错误右边界未设为总水量/n分组逻辑错误未按「i k」遍历组内瓶子。