wqs二分学习笔记

适用范围

wqs 二分的题目通常需要你通过固定的操作次数去得到某个最大值/最小值。
wqs 二分需要题目满足凸函数的性质。
这里的凸函数是一个以操作次数为 \(x\) 轴，以结果为 \(y\) 轴，斜率单调递减或者递增。
至于怎样才是凸的，就是要求斜率单调的情况下才是凸的。
比如一次操作是结果加上一个可以选择的数字，那么斜率就是每次选择的数字，贪心处理就是会单调递减。
比较经典的还有可以使用网络流做的基本都是符合凸函数的性质的，所以模拟费用流的题很多也可以使用wqs二分来做。
具体操作

综上可知，我们能够二分斜率。
通过二分这个斜率，我们把一次操作视为带有了这个斜率的代价。
那么我们就可以忽略操作的次数来处理。
但是我们也要记录到达最终状态时的操作次数，然后通过这个次数判断二分的方向。
剩下一个难点在如果结果相同，应该选择次数少的还是多的。

这个其实看的是你在 check 的时候是判断 >= 还是

鼓励转贴优秀软件安全工具和文档！