【学习笔记】01分数规划

01分数规划是这样的一类题目： 给你n项物品，每项物品有一个$value$和一个$cost$,要求从这些物品中按照要求选出一些项使得$\frac{\sum{value}_i}{\sum{cost}_i}$尽量大 对于这类问题，我们设一个值$x$，当$x$可以被取到时，则有 $$\large\frac{\sum{value}_i}{\sum{cost}_i}\ge x$$ 很明显这个东西具有单调性，可以考虑二分。 先对上面的式子做一下变式： $${\frac{\sum{value}_i}{\sum{cost}_i}\ge x}$$ $$=>\sum{value}_i \ge {(\sum{cost}_i)}*x$$ $$=>\sum{value}_i-{(\sum{cost}_i)}*x\ge0$$ $$=>{(\sum{cost}_i)}*x-\sum{value}_i\le0$$ 于是一个值能作为答案的充要条件就是有一种选法，使其满足上式。 那么我们每次二分时把每项物品的值设为${(\sum{cost}_i)}*x-\sum{value}_i$，然后考虑有没有一种选法使得选出的值的总和为负数就可以了。 这样做的好处就在于把不能加减的比率，转化成了可以直接求解，可以加减的值，可以方便地求解。 一些例题： [luoguP2868 sightseeing cows](https://www.luogu.org/blog/PopulusEuphratica/luogup2868-usaco07dec-guan-guang-nai-niu-sightseeing-cows) [luoguP3705 新生舞会](https://www.luogu.org/blog/PopulusEuphratica/luogup3705-sdoi2017-xin-sheng-wu-kuai) [luoguP2989 [USACO10MAR]对速度的需要Need For Speed](https://www.luogu.org/blog/PopulusEuphratica/luogup2989-usaco10mar-dui-su-du-di-xu-yao-need-for-speed)