【poj2976】$Dropping\ tests$——初步接触分数规划

题目大意

给出两个有$n$个元素的序列$A,B$

分别选择$n-k$个元素，询问$\frac{\sum a_i}{\sum b_i}$的最大值

数据范围

$1\leqslant n\leqslant 1000,0\leqslant k< n$

题解——二分

入门题是一道裸题，就不会把人吓跑啦

设，$x=\frac{\sum a_i}{\sum b_i}\ \rightarrow\ \sum a_i-x\times \sum b_i=0$

令，$f(x)=max(\sum a_i-x\times \sum b_i)$，可以得到$f(x)$是一个单调递减的函数

新函数是非分式的规划，有以下性质

设，原规划最优解为$x^{\prime}$

1. $f(x)> 0\ \leftrightarrow\ x< x^{\prime}$

2. $f(x)= 0\ \leftrightarrow\ x= x^{\prime}$

3. $f(x)< 0\ \leftrightarrow\ x> x^{\prime}$

然后给出简略的证明

$f(x)>0$，也就意味着存在$\sum a_i-x\times \sum b_i>0\ \rightarrow\ \frac{\sum a_i}{\sum b_i}>x$，则肯定有更优解，即$x< x^{\prime}$

另外两个，也是类似的证法，这里不详细给出

然后怎么来做这道题呢?

$f(x)$是单调递减的函数，因此可以每次二分$x$

然后处理得到$a_i-x\times b_i$，再排序得到最大的$n-k$个值，求和就是$f(x)$

最后利用性质判断，继续二分即可

阅读更多……