浅谈WQS二分

WQS二分学习笔记

• WQS二分学习笔记
  • 用途：
  • 思考方式：
    • 使用限制：
    • 算法思想：

用途：

WQS二分通常用来解决形如强制选k个且收益最大/代价最小的题目。
就比如说：https://www.luogu.com.cn/problem/P5308
如果没有限制的话，代码会非常简单

思考方式：

使用限制：

首先要使用WQS二分要有限制：便是最终k与ans(k)构成的函数是一个凸壳。
至于想要证明某一题凸壳成立，三种方法：

1. 设两到三个数i,j,k推式子。
2. 感性理解。
3. 暴力打表输出（加一维来表示k)。
   强烈推荐第三种。
   但在这里就不好说了，可以这么分析：
   假设我有一道题要找恰好k时的最大值。
   那你就只需要感性理解下去少于k次不优，取大于k次且ans(k+p)>ans(k)不存在就好了。
   后面这半句常采用反证法分析（不然的话可以通过交换什么的让答案更优）

算法思想：

竟然形成了凸壳，那么十有八九和这个图脱离不了干系。
这种凸壳有什么共同关系呢？
当横坐标x单调递增时，发现斜率也是单调递增或者单调递减的。既然单调，就可二分。

我们假设有了一个上凸壳，要找最大值。
假设我们有一个斜率为c的直线去切所有的(k,ans_k)这些点，若不考虑共线的情况，最终存在一个切点，使这条线除了切点不会与凸壳有其他交点。
我们就考虑这个特殊点，最终他肯定也会和y轴有个纵截距。
代入ans_k和k可以得到，这个纵截距b=ans_k-c*k。
这个东西拆开来看，我进行k次操作时，每一次操作都会使最终答案减少c。
然后就会有这样一个结论：切点上的ans_k为所有选取的价值都减少c后的全局最优解。
于是我们就可以在每一次二分斜率 c 后，直接求出当前每个白边边权减小 c 后任意选的最优解，同时记录最优解需要的选取的数量 x，再把价值加上 c⋅x 就得到了所需的数据。
那么很明显的是，当限制为k时，上文的x自然就是k。