题目链接：click here~~

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

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

代码：

//#include <bits/stdc++.h>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <iostream>

#include <algorithm>

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<n; i++) pp[i].y=pp[i].v-mid*pp[i].w;

    sort(pp,pp+n,cmp);   //从大到小排序

    double sum=0;

    for(int i=0; i<k; i++)

        sum+=pp[i].y;//从大往小选择

    if(sum>=0) pk=true;

    else pk=false;

    return pk;

}

int main()

{

    //freopen("1.txt","r",stdin);

    scanf("%d%d",&n,&k);

    for(int i=0; i<n; i++){

        scanf("%lf%lf",&pp[i].v,&pp[i].w);

        pp[i].id=i+1;

    }

    double ll=0,rr=1e8;

    while(fabs(ll-rr)>eps)

    {

        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<k;i++)

    printf(" %d",pp[i].id);

    puts("");

}