这道题可以用排序,但是这道题可以用来理解 wqs 二分 的思路.
但是有了准确的次数限制之后就行不通了.
wqs 二分的作用就是能利用这个和 \(k\) 与答案关系 的斜率的单调性,二分一条直线的斜率来切凸包.
形象地理解,加上代价之后凸包变形,求变形凸包的最高点等同于原来用 \(c\) 斜率的直线切凸包,切出来就是最大的截距.
当然这只是一个思想,还有许多细节需要注意.
买卖股票的最佳时机 IV
套用上面的套路可以发现,答案与限制条件之间的关系是满足 \(k\) 与答案关系 的斜率有单调性,加上代价后的答案可以使用线性的 DP 或贪心计算.
由于我们知道答案都是整数,斜率只需要二分整数就行了,一定能二分到 \(k\) 的一段.
这就要说一个很恶心的情况了.如果凸包上三点共线,我们只能取到上面的一些特殊点(如最左最右的点),不一定取到 \(k\);如果读者想要尝试,本题目中以下样例存在该情况:
这道题完美符合上述特点,同样需要注意三点共线情况.写法同样有两种.