写在前面：
放假之前水篇博客 = =
问题描述
给定一个二元组 \((value_i,cost_i)\) ，\(value_i\) 是选择此二元组获得的价值（非负），\(cost_i\) 是这个二元组的代价（非负），设 \(x_i (x_i \in {0, 1})\) 表示第 \(i\) 个二元组选不选，最大化(最小化)下面柿子
\[max(min)~r = \frac{\sum value_i * x_i}{\sum cost_i * x_i} \]
下面以最大值为例（最小值也一个样）
\[max_r = \frac{\sum value_i * x_i}{\sum cost_i * x_i}\\ ~~\\ \sum value_i * x_i - maxr * \sum{cost_i * x_i} = 0 \]构造一个函数
\(f(r) = \sum value_i * x_i - r * \sum{cost_i * x_i}\)
对于如果 \(x_i\) 确定那么 \(f(r)\) 就成了 \(f(r) = -kr + b\) 的一条直线 \(k, b\) 都为常数
因为 \(value_i\) 和 \(cost_i\) 都非负，所以 \(k, b > 0\) ，所有直线都是一条斜率为负，纵截距为正的直线
画出来是这样的
求最大的 \(r\) 就是求一条横截距最大的直线
求一条垂直于 \(y\) 的线
- 如果存在直线与这条直线的交点纵坐标为正，则最优解在该直线右边
- 如果所有直线与这条直线的交点纵坐标为负，则最优解在该直线左边
- 如果一条直线与该直线交点纵坐标为 0，其余都为负，则该交点横坐标为最优解 \(max_r\)
具体实现
对 \(r\) 二分答案
-
\(max(f(r)) > 0\) ，\(max_r > r\) 二分右区间
-
\(max(f(r)) < 0\)， \(max_r < r\) 二分左区间
-
\(max(f(r)) = 0\) ，\(max_r = r\) 统计答案
接下来就剩怎么求 \(max(f(r))\) 了
对上面的柿子稍微变一下形
\(f(r) = \sum (value_i - r * cost_i)*x_i\)
对于前面的一坨如果知道了 \(r\) 可以直接求，然后现在就是找一组 \(x_i\) 使得 \(f(r)\) 最大，怎么求这一组 \(x_i\)，要根据具体题目分析
常见模型：最优比率生成树，最优比率环，最大密度子图