只能说确实挺基础。
集合起来写写吧。
二分系列
二分
略。
三分
对于传统的定义域在实数上的凸函数求最值，可以使用三分法。
lmid = l + ((r - l) >> 1);
rmid = lmid + ((r - l) >> 1);
if(cal(limd) > cal(rmid))
r = rmid;
else
l = lmid;
对于凸函数的二分
OI里凸函数大多为横坐标差相等的离散函数，我们知道凸函数的导数有单调性，又知OI里是离散的，所以我们直接
二分位置，求\(\Delta\to 0\)的位置即最值位置。
分数规划
一般来说分数规划求如下问题
若干物品有两个权值\(a,b\),选出若干物品使得\(\frac{\sum a}{\sum b}\)最小/最大。
同时可能会有一些奇怪的限制，比如“分母至少为\(W\)”，我会在这个学习笔记配套的练习里说。
我们对该问题采取二分法。
二分答案后我们转为\(check\)。
求\(\frac{\sum a}{\sum b} > mid\)
即可知\(\sum a - mid * \sum b > 0\)
即\(\sum a - mid * b > 0\)
求出左侧柿子最大值即可。