题目大意：挑选k个珠宝使得∑a/∑b最大，输出组合数
最大化平均值的标准题型，二分法就好了，一定要注意范围（10e-7），如果是10e-8就会tle，10e-6就是wa
#include <iostream>
#include <functional>
#include <algorithm> using namespace std;
struct _set
{
int v, w, num;
}jewels[];
struct _out_set
{
double price;
int num;
bool operator<(const _out_set &x)const
{
return price < x.price;
}
}y[];
static int s2[]; bool judge(double, const int, const int); int main(void)//最大化平均值标准题型，要求输出组合
{
int n, k;
double lb, rb, mid; while (~scanf("%d%d", &n, &k))
{
for (int i = ; i < n; i++)
{
scanf("%d%d", &jewels[i].v, &jewels[i].w);
jewels[i].num = i + ;
}
lb = ; rb = 10e++; for (; rb - lb > 10e-;)//精度起码10e-7以上，不能10e-8,不然tle
{
mid = (lb + rb) / ;
if (judge(mid, n, k))lb = mid;
else rb = mid;
}
for (int i = ; i < k; i++)
printf("%d ", s2[i]);
printf("\n");
}
return ;
} bool judge(double mid, const int n, const int k)
{
double sum = ;
for (int i = ; i < n; i++)
{
y[i].price = jewels[i].v - mid*jewels[i].w;
y[i].num = jewels[i].num;
}
sort(y, y + n);//内建排序一定要对，不然又要出错了T T for (int i = ; i < k; i++)
{
sum += y[n - i - ].price;
s2[i] = y[n - i - ].num;
}
return sum >= ;
}