WQS二分法学习笔记有哪些要点可以分享？

本文共计1612个文字，预计阅读时间需要7分钟。

什么是引入是什么？能用来解决什么问题？序列 \((a)\) 有 \(n\) 个元素，求选择 \(k\) 个元素和的最大值？这个问题可以用排序来解决，但也可以用来理解 wqs 和二分的思路。用 \((g_k)\) 表示选择的“最佳元素。”

引入 是什么？ 能用来解决什么问题？

序列 \(a\) 有 \(n\) 个元素，求选正好 \(k\) 个元素和的最大值？

这道题可以用排序，但是这道题可以用来理解 wqs 二分 的思路。
用 \(g_k\) 表示选恰好 \(k\) 个元素的最佳答案，把 \((k,g_k)\) 形成的点画在坐标系上，就能得到一个「上凸包」。

例如 \(a = [9,8,4,2,-9,-15]\) 时，

对于大多数题目，如果没有 \(k\) 的限制（即取的次数的限制），应该是可以在可观的复杂度内如 \(\mathcal{O}(n)\) 得出答案，比如这道题就是把所有正数加起来，答案相当于求凸包的最高点纵坐标。
但是有了准确的次数限制之后就行不通了。

wqs 二分的作用就是能利用这个和 \(k\) 与答案关系 的斜率的单调性，二分一条直线的斜率来切凸包。

什么是切凸包？

wqs 二分的 check 环节在切凸包。