- 题目描述：给\(n\)个物品，每个物品有两个属性\(v_i\)和\(c_i\)，选出其中\(m\)件，最大化\(\frac{\sum v_i}{\sum c_i}\)。
- 数据范围：\(1≤m≤n≤200\)，\(1≤c_i,v_i≤1×10^4\)。
01分数规划的板子题，不过很久没写过了还是记录一下。
对于一个数值\(\lambda\)，验证其是否符合条件是更为容易的。例如我们需要验证是否存在一种选法使得\(\frac{\sum v_i}{\sum c_i}\ge \lambda\)，由于\(c_i\)非负，简单变换一下就是\(\sum\left(v_i-\lambda c_i\right)\ge 0\)，那么将\(v_i-\lambda c_i\)排序后看最大的\(m\)个之和是否非负即可。
时间复杂度为\(O(n\log v)\)，\(v\)为值域。
- 题目描述：给定\(n\)个数\(\{a_n\}\)，现在要选出一些数，满足任意两个相邻的数中至少有一个数被选择。求出所有选择方案中，被选中数字平均值和中位数的最大值（偶数\(2k\)个数的中位数视作第\(k\)小的数） 。
- 数据范围：\(2\le n\le 10^5\)，\(1\le a_i\le 10^9\)。
感觉这类求平均值的题目二分的可能性很大。
对平均值，需最大化\(\frac{\sum a_{i}}{k}\)（\(k\)是选数的数量），是一个01分数规划的模型，对于\(\frac{\sum a_{i}}{k}\ge\lambda\)可以转换为\(\sum(a_i-\lambda)\ge0\)，记\(c_i=a_i-\lambda\)，看是否存在一种选法使\(\sum c_i\ge 0\)即可。
令\(f_i\)为目前到\(i\)且必须选\(i\)能取得的最大\(\sum c_i\)值，那么转移为\(f_i=\max\{f_{i-1},f_{i-2}\}+c_i\)，最后\(\max\{f_{n-1},f_{n}\}\)即是答案。
dsf
df
dsf
dsf
dsf
dsf