科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本文精读 codeforces-go 仓库中 LeetCode 第 325 场周赛 C 题leetcode/weekly/325/c/README.md的完整解法深入剖析「最大化最小值 / 最小化最大值」类问题的通用套路先对价格排序把「任意两种糖果价格绝对差的最小值」转化为「相邻价格差的最小值」再借助答案的单调性二分配合 O(n) 的贪心判定函数求解。读完你将掌握二分答案的标准模板、开区间二分的端点设置与循环不变量写法并看到该仓库中对应的 Go 实现、测试数据与测试框架调用链。题目与核心转化最小值怎么拆解题目要求从price中选出k类糖果放入礼盒使礼盒中任意两种糖果价格绝对差的最小值即「甜蜜度」尽可能大。第一个关键观察是「任意两种糖果价格绝对差的最小值」等价于「排序后任意两种相邻糖果价格绝对差的最小值」。这是因为数组排序后任意两元素的最小绝对差一定出现在某对相邻元素之间。因此先把price从小到大排序问题就变成在有序数组里选k个位置使选出的相邻位置间距的最小值最大化。为什么可以二分答案最大化最小值问题与单调性如果题目要求「最大化最小值」或者「最小化最大值」一般优先考虑二分答案。原因是这类目标函数通常具有单调性甜蜜度最小间距要求设得越大能同时满足要求的糖果就越少甜蜜度设得越小可选的糖果就越多。即「甜蜜度上限 → 可选数量」构成单调递减关系于是答案可以用二分逼近。关于二分答案的原理可参考作者在 B 站「基础算法精讲 04」中的讲解二分答案/最大化最小值/最小化最大值是竞赛中的高频模型。定义判定函数$$ f(d)\text{甜蜜度至少为 }d\text{ 时最多能选多少类糖果} $$注意是至少不是恰好。于是二分答案d的规则非常清晰如果 $f(d)\ge k$说明答案至少为 $d$可以继续增大 $d$如果 $f(d)k$说明答案至多为 $d-1$需要缩小 $d$二分结束后设答案为 $d_0$则有 $f(d_0)\ge k$ 且 $f(d_01)k$即 $d_0$ 是满足 $f(d)\ge k$ 的最大值。判定函数 f(d)排序后的贪心如何计算 $f(d)$对price从小到大排序后用贪心即可第一个数price[0]一定可以选。理由如果有方案不选price[0]把该方案中的第一个数改成price[0]间距只会更小、不会破坏要求或者说选price[0]后后面可选的空间比不选它更大不会更差。假设上一个选的数是pre那么只有当price[i] pre d时才可以选择price[i]。这里取「满足条件的最靠前元素」能留出最大的剩余空间是贪心正确性的关键每次选择最小的可行位置等价于给后续留下最多的余地。每步至多线性扫描一遍数组因此 $f(d)$ 的计算复杂度为 $O(n)$。判定函数写成代码def f(d: int) - int: cnt 1 pre price[0] # 先选一个价格最小的糖果 for p in price: if p - pre d: # 可以选 p cnt 1 pre p return cnt二分细节开区间端点的初始化与循环不变量文档采用开区间二分这仅仅是二分的一种写法使用闭区间或半闭半开区间同样可行。关键是把握两个端点的含义开区间左端点初始值$0$。此时计算的是 $f(0)$表示甜蜜度至少为 $0$ 时最多能选多少类糖果。由于任意价格差的绝对值一定 $\ge 0$所以所有糖果都可以选一定满足 $f(0)\ge k$题目保证 $k\le n$。开区间右端点初始值$\left\lfloor\dfrac{\textit{price}[n-1]-\textit{price}[0]}{k-1}\right\rfloor1$。推导思路假设每隔 $d$ 就选一类糖果那么第 1 个糖果和第 $k$ 个糖果的间隔至少为 $(k-1)\cdot d$必须满足$$ \textit{price}[0] (k-1)\cdot d \le \textit{price}[n-1] $$才可能选满 $k$ 个糖果解得$$ d \le \left\lfloor\dfrac{\textit{price}[n-1]-\textit{price}[0]}{k-1}\right\rfloor $$所以在这个上界的基础上加一就一定无法满足要求即 $f(d_{\text{right}})k$ 恒成立。循环不变量贯穿整个二分过程f(left) k f(right) k每次取mid (left right) / 2若f(mid) k令left mid下一轮二分区间为(mid, right)否则令right mid下一轮区间为(left, mid)。当left 1 right开区间为空时循环结束返回left即最大的满足 $f(\textit{left})\ge k$ 的数。常见疑问答案一定是数组中的价格差吗问为什么二分出来的答案一定来自数组中价格的差有没有可能二分出来的答案不是任何价格的差答用反证法。如果答案 $d$ 不是任何价格的差也就是说礼盒中任意两种糖果的价格的绝对差都大于$d$即都大于等于$d1$。那么对于 $d1$ 来说它也满足 $f(d1)\ge k$这与循环不变量$d$ 是满足 $f(d)\ge k$ 的最大值相矛盾。因此原命题成立二分答案必然收敛到某个真实存在的价格差。多语言参考实现以下代码完整覆盖了 Python、Java、C、C、Go、JavaScript、Rust 七种语言可直接替换运行class Solution: def maximumTastiness(self, price: List[int], k: int) - int: def f(d: int) - int: cnt 1 pre price[0] # 先选一个价格最小的糖果 for p in price: if p - pre d: # 可以选 p cnt 1 pre p return cnt price.sort() left 0 right (price[-1] - price[0]) // (k - 1) 1 while left 1 right: # 开区间不为空 # 循环不变量 # f(left) k # f(right) k mid (left right) // 2 if f(mid) k: left mid # 下一轮二分 (mid, right) else: right mid # 下一轮二分 (left, mid) return left # 最大的满足 f(left) k 的数class Solution: def maximumTastiness(self, price: List[int], k: int) - int: def check(d: int) - bool: # 二分最小的 f(d1) k从而知道最大的 f(d) k d 1 cnt 1 pre price[0] # 先选一个价格最小的糖果 for p in price: if p - pre d: # 可以选 p cnt 1 pre p return cnt k price.sort() right (price[-1] - price[0]) // (k - 1) return bisect_left(range(right), True, keycheck)class Solution { public int maximumTastiness(int[] price, int k) { Arrays.sort(price); int left 0; int right (price[price.length - 1] - price[0]) / (k - 1) 1; while (left 1 right) { // 开区间不为空 // 循环不变量 // f(left) k // f(right) k int mid left (right - left) / 2; if (f(price, mid) k) { left mid; // 下一轮二分 (mid, right) } else { right mid; // 下一轮二分 (left, mid) } } return left; // 最大的满足 f(left) k 的数 } private int f(int[] price, int d) { int cnt 1; int pre price[0]; // 先选一个价格最小的糖果 for (int p : price) { if (p - pre d) { // 可以选 p cnt; pre p; } } return cnt; } }class Solution { public: int maximumTastiness(vectorint price, int k) { auto f - int { int cnt 1, pre price[0]; // 先选一个价格最小的糖果 for (int p : price) { if (p - pre d) { // 可以选 p cnt; pre p; } } return cnt; }; ranges::sort(price); int left 0; int right (price.back() - price[0]) / (k - 1) 1; while (left 1 right) { // 开区间不为空 // 循环不变量 // f(left) k // f(right) k int mid left (right - left) / 2; (f(mid) k ? left : right) mid; } return left; // 最大的满足 f(left) k 的数 } };int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; } int maximumTastiness(int* price, int priceSize, int k) { int f(int d) { int cnt 1, pre price[0]; // 先选一个价格最小的糖果 for (int i 1; i priceSize; i) { if (price[i] - pre d) { // 可以选 p cnt; pre price[i]; } } return cnt; } qsort(price, priceSize, sizeof(int), cmp); int left 0; int right (price[priceSize - 1] - price[0]) / (k - 1) 1; while (left 1 right) { // 开区间不为空 // 循环不变量 // f(left) k // f(right) k int mid left (right - left) / 2; if (f(mid) k) { left mid; } else { right mid; } } return left; // 最大的满足 f(left) k 的数 }func maximumTastiness(price []int, k int) int { slices.Sort(price) return sort.Search((price[len(price)-1]-price[0])/(k-1), func(d int) bool { d // 二分最小的 f(d1) k从而知道最大的 f(d) k cnt, pre : 1, price[0] for _, p : range price[1:] { if p-pre d { cnt pre p } } return cnt k }) }var maximumTastiness function(price, k) { function f(d) { let cnt 1, pre price[0]; // 先选一个价格最小的糖果 for (const p of price) { if (p - pre d) { // 可以选 p cnt; pre p; } } return cnt; } price.sort((a, b) a - b); let left 0; let right Math.floor((price[price.length - 1] - price[0]) / (k - 1)) 1; while (left 1 right) { // 开区间不为空 // 循环不变量 // f(left) k // f(right) k const mid Math.floor((left right) / 2); if (f(mid) k) { left mid; } else { right mid; } } return left; // 最大的满足 f(left) k 的数 };impl Solution { pub fn maximum_tastiness(mut price: Veci32, k: i32) - i32 { price.sort_unstable(); let f |d: i32| - i32 { let mut cnt 1; let mut pre price[0]; // 先选一个价格最小的糖果 for p in price { if p - pre d { // 可以选 p cnt 1; pre p; } } cnt }; let mut left 0; let mut right (price.last().unwrap() - price[0]) / (k - 1) 1; while left 1 right { // 开区间不为空 // 循环不变量 // f(left) k // f(right) k let mid left (right - left) / 2; if f(mid) k { left mid; } else { right mid; } } left // 最大的满足 f(left) k 的数 } }复杂度分析时间复杂度$\mathcal{O}(n\log n n\log U)$其中 $n$ 为price的长度$U\dfrac{\max(\textit{price})-\min(\textit{price})}{k-1}$。排序 $O(n\log n)$二分最多 $\log U$ 轮每轮判定 $O(n)$。空间复杂度$\mathcal{O}(1)$忽略排序的栈开销。仓库内的 Go 实现与测试验证该题在仓库中有完整的实现、测试数据与自动化测试入口可以本地直接运行验证实现leetcode/weekly/325/c/c.go 使用slices.Sort排序并用sort.Search封装「二分最小的 $f(d1)k$」的库函数写法与 README 中sol-Go完全一致func maximumTastiness(price []int, k int) int { slices.Sort(price) return sort.Search((price[len(price)-1]-price[0])/(k-1), func(d int) bool { d // 二分最小的 f(d1) k从而知道最大的 f(d) k cnt, pre : 1, price[0] for _, p : range price[1:] { if p-pre d { cnt pre p } } return cnt k }) }测试数据leetcode/weekly/325/c/c.txt 内置三组样例覆盖常规、重复价格答案为 0等场景[13,5,1,8,21,2] 3 8 [1,3,1] 2 2 [7,7,7,7] 2 0测试入口leetcode/weekly/325/c/c_test.go 通过testutil.RunLeetCodeFuncWithFile从c.txt读取输入输出并逐组断言该函数定义于 leetcode/testutil/leetcode.go。运行go test ./leetcode/weekly/325/c/即可复现三组样例的通过结果。分类与延伸本题属于经典的「二分答案二分答案/最小化最大值/最大化最小值/第K小」题单模型与「滑动窗口与双指针」「贪心与思维」等分类互相配合。同一场周赛Weekly Contest 325的其他题目也位于 leetcode/weekly/325/ 目录下a/b/c/d 四题各有 README 题解、实现与测试文件可作为同一批单调性、贪心、DP 技巧的配套练习例如 A 题环形数组最近目标、B 题两端取字符的滑动窗口补集技巧、D 题 01 背包正难则反计数。若想系统化训练二分答案可直接在仓库内按题单搜索对应题解并结合 copypasta/search.go 中封装的二分工具函数加深理解。总结一下整题的思维链排序消除「任意两两」的复杂性 → 识别最大化最小值的二分结构 → 用「至少为 d 时最多能选多少」作为单调判定函数 → 贪心 O(n) 求 f(d) → 开区间二分收敛到真实价格差。这一套流程可以原样迁移到大量「最大化最小值 / 最小化最大值」问题上。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐二分答案 贪心判定LeetCode 410「分割数组的最大值」最小化最大值模板全解codeforces-go 仓库实战二分答案 贪心判定LeetCode 410「分割数组的最大值」最小化最大值模板全解codeforces go 仓库实战 本文以 leetcode/pr科学计算codeforces-go中的二分答案最大化最小值问题codeforces go中的二分答案最大化最小值问题 你是否在解决算法问题时遇到过这样的场景需要在一系列约束条件下找到一个最优解使得某个值尽可能大同科学计算AlgoNote 算法题解LeetCode 0410 分割数组的最大值——用二分答案 贪心验证攻克最小化最大值问题AlgoNote 算法题解LeetCode 0410 分割数组的最大值——用二分答案 贪心验证攻克最小化最大值问题 本篇以 AlgoNote「算法通关教程文档知识库上一篇从实验到稳定etcd客户端SAN验证跳过机制的演进之路下一篇AetherArenaADR-149构建厂商中立的 WiFi 空间智能基准——公开计分、私有评测集与防篡改结果链创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考