POJ 3111 K Best(最大化平均值)

【题目大意】有n个物品的重量和价值各自是Wi和Vi。从中选出K个物品使得单位重量的价值最大，输出物品的编号

【解题思路】：最大化平均值的经典.參见click here~~

代码：

//#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N=1e5+10;
const double eps=1e-8;
int n,k,m;
struct node
{
    double y,v,w;//价值。重量
    int id;
}pp[N];
bool cmp(node a,node b)
{
    return a.y>b.y;
}
bool get(double mid)//能够选择使得单位重量的价值不小于mid
{
    bool pk;
    for(int i=0; i=0) pk=true;
    else pk=false;
    return pk;
}
int main()
{
    //freopen("1.txt","r",stdin);
    scanf("%d%d",&n,&k);
    for(int i=0; ieps)
    {
        double mid=(ll+rr)/2;
        if(get(mid)) ll=mid;
        else rr=mid;
    }
    //printf("%.2f\n",rr);
    printf("%d",pp[0].id);
    for(int i=1;i