三分法#

求函数的极值. 结论: 如果若干个函数均为单极小值函数, 则他们取max也是单极小值函数. 例题: 1730B 285083A

01分数规划#

形式化表述: 给定两个数组A, B. 求一组$w_i\in \set{0, 1}$, 最小化或最大化$\frac{\sum a_iw_i}{\sum b_iw_i}$.

通俗地讲, 这相当于每个物品有两个权值a, b. 取若干个物品, 求a的总和与b的总和的比值.

这类问题通常可以用二分法来解决. 对于每个预测值mid, 我们应该考虑$\sum a_iw_i$与$\sum b_iw_i$的比值是否大于等于mid. 这等价于求某个子集使得$\sum (a_i - mid \times b_i) \ge 0$. 求出左式最大值即可.

例题: 285069A 285069C(nth_element的用法: nth_element(first, nth, last), 其中first, nth, last均为迭代器, 这个函数保证nth位置的数值准确, nth前全部小于nth, nth后全部大于nth. 平均O(n)的复杂度)