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 环节在切凸包。

有了一个确定斜率 \(c\) 的直线之后，假设与凸包切在一个点 \((p,g_p)\)，那么此时一定满足直线的「截距」最大，为 \(g_p-c\cdot p\)。