题意：
最大化平均值的模型：
有N个物品的重量和价值分别为Wi和Vi，从中选取K个物品使得单位重量的价值最大。也就是使得K个物品的ΣVi /ΣWi最大。
使用二分搜索解决这类问题：
ΣVi /ΣWi >= x也就是Σ(Vi-x*Wi)>=0
去找最大的可行解x即可！X越大，式子左边越小，一直逼到=0的边界！
本题属于这个模型！只不过最后让输出的是选出来的是哪些物品，一样的，对Vi-X*Wi排序的前K个就是所求的物品。
题解：
最大化可行解。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>using namespace std;int M,K;
const int INF=1e7+1;struct node
{int v,w,id;double y;
};
struct node a[100000+5];bool cmp(struct node n1,struct node n2)
{return n1.y>n2.y;
}bool C(double x)
{for(int i=0; i<M; i++)a[i].y=a[i].v-x*a[i].w;sort(a,a+M,cmp);double sum=0;for(int i=0; i<K; i++)sum+=a[i].y;return sum>=0;}int main()
{cin>>M>>K;for(int i=0; i<M; i++){ scanf("%d%d",&a[i].v,&a[i].w);a[i].id=i+1;}double lb=0,ub=1.0*INF;for(int i=1; i<100; i++){double mid=(lb+ub)/2;if(C(mid))lb=mid;else ub=mid;}for(int i=0;i<K;i++)printf("%d ",a[i].id);printf("\n");}