题意：
给n个元素，每个元素有两个属性（v,w）,现在要从中选k个，使sum(v)/sum(k)最大。
分析：
参数搜索的入门题，牛顿迭代比二分快很多。
代码：
//poj 3111
//sep9
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxN=100024;
int n,k;
double s0,s1;
struct Node
{int v,w;double tmp;int ids;bool operator<(const Node& x)const{return tmp>x.tmp;}
}a[maxN];double get_v()
{int sum_v=0,sum_w=0;for(int i=0;i<k;++i)sum_v+=a[i].v,sum_w+=a[i].w; return sum_v*1.0/sum_w;
}int main()
{scanf("%d%d",&n,&k);for(int i=0;i<n;++i){scanf("%d%d",&a[i].v,&a[i].w);a[i].ids=i+1; }s0=get_v(); while(1){for(int i=0;i<n;++i)a[i].tmp=a[i].v-s0*a[i].w;nth_element(a,a+k,a+n);s1=get_v(); if(fabs(s0-s1)<1e-8)break;s0=s1; }printf("%d",a[0].ids);for(int i=1;i<k;++i)printf("% d",a[i].ids);return 0;
}