二分，排序，贪心。
最优比率生成树，可以二分$+$贪心来实现，不过这样做精度不行。
如果是这样一个问题，该如何解决：问你$n$个里面选择$k$个，能否使得$\frac{
{\sum\limits_{j = 1}^k {
{v_{
{i_j}}}} }}{
{\sum\limits_{j = 1}^k {
{w_{
{i_j}}}} }} ≥ x$。
上述问题等价于问你：$n$个里面选择$k$个，能否使得$\sum\limits_{j = 1}^k {({v_{
{i_j}}} - x×{w_{
{i_j}}})} ≥ 0$。
也就是说，我们需要令${f_i} = {v_i} - x×{w_i}$，按照${f_i}$从大到小排序，选择前$k$个计算和$sum$。
如果$sum≥0$，也就是说$\frac{
{\sum\limits_{j = 1}^k {
{v_{
{i_j}}}} }}{
{\sum\limits_{j = 1}^k {
{w_{
{i_j}}}} }} ≥ x$成立；否则不成立。
因为这个问题是遵循单调性的，$x$越大可能性越小，因此只要二分$x$，然后验证就可以了。时间复杂度$O(50*n*\log n)$。
特别要注意的是精度问题：
$[1].$计算$sum$的时候，最后要加上一个$eps$，我在这卡了很久精度。
$[2].$二分的话差不多$50$次就可以了，$100$次$TLE$了，也没有必要进行$100$次，因为实际上是只要$\log {10^7}$次。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include