如果没有段数限制,那我们肯定是每个数分成一段对吧.
如果加上段数限制呢?
先放上结论:打表可得如果以段数 \(k\) 为横坐标,以该段数求得的最小和 \(f(k)\) 为纵坐标,把这 \(n\) 个点放在平面直角坐标系上,那么形成的图形会是一个上凸包.也就是相邻两点的斜率单调不增.
还有一个问题没有解决,如果我们二分不出来这个具体的 \(k\) 怎么办,也就是说,凸包上出现三点共线的情况怎么办.
给你一个无向带权连通图,每条边是黑色或白色.让你求一棵最小权的恰好有 \(k\) 条白色边的生成树.题目保证有解.
这里有一个细节就是会出现白边和黑边边权相等的情况,这时候就要用到上边的做法,强制规定一个规则.假设我们规定相等时先用白边,那二分就这么写:
if(used>=k) ans=midl=mid+1;
把这个式子拿出来推一推,发现这就是个斜率优化的式子了.
有 \(a\) 个宝贝球和 \(b\) 个大师球.对于每个神奇宝贝,用宝贝球抓到的概率为 \(p_i\),用大师球抓到的概率为 \(q_i\) (咦不是100%吗) .不能对一个神奇宝贝用多个相同种类的球,但是可以既用宝贝球又用大师球.问最优方案下期望抓到的神奇宝贝数量.
这里也有在凸包上三点共线的问题,解决方案就是,因为我们最大化了选出的链数,所以在二分过程中,选出的链数如果 \(>=k\) ,那就得记录当前的 \(mid\) 了.