POJ 3111 K Best最大化平均値(二分)

タイトルリンク:http://poj.org/problem?id=3111
n個のジュエリー、それぞれのジュエリーは1つの重量wiと価値viに対応して、今中からk個を探し出して、このk個のジュエリーの単位重量の価値を最大にして、このk個のジュエリーの番号を出力します.
分析:一般的に最初に考えられる方法は、物品を単位価値で並べ替え、大きいものから小さいものまで検索することかもしれないが、このようにして、実際に求められるのは与えられた重量に対して、得られる最大の価値であり、明らかに本題が要求しているものではない.
      実際には、得られる可能性のあるすべての価値を二分し、そこから最大の価値を見つけることができます.条件C(x)=を定義して、単位重量の価値がxより小さくないように選択することができ、このように元の問題はC(x)の最大のxを満たすようにする.C(x)をどう判断すればいいのでしょうか.もし我々がある物の集合Sを選んだならば、彼の単位重量の価値はΣvi/Σwiであるので、Sが満足しているか否かを判断するために変化する:Σvi/Σwi>=x、簡略化してΣ(vi-x*wi)>=0を得ることができるので、yi=(vi-x*wi)の値を並べ替えて貪欲に選択することができるので、問題は判断条件になる      C(x)=yi降順で配列された最初のk個の和は0以下である 成立したかどうか.時間的複雑度はO(n logn)であった.
実装コードは次のとおりです.

#include 
#include 
using namespace std;
const int M=1e5+10;
const double inf=99999999.0;
struct node
{
    int v,w,id;
    double y;
    bool operator a.y;
    }
}jew[M];
int n,k;
bool judge(double x)
{
    for(int i=0;i=0;
}
void solve()
{
    double left=0,right=inf;
    for(int i=0;i<100;i++)
    {
        double mid=(left+right)/2;
        if(judge(mid)) left=mid;
        else right=mid;
    }
    for(int i=0;i