POJ 3111 K Best （最大化平均值，贪心 二分）难度⭐⭐⭐

题目来源：
【题意】
有n个物品的重量和价值分别是wi，vi，从中选取k个物品使得单位重量的价值最大。
输出格式：
输出一行物品的编号。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
using namespace std;
typedef long long ll;
const ll N=1e5+7;
const double mod=2147483647.0;
const double EPS=1e-6;
ll n,k;
double f[N];
#undef mid
struct node
{
    double v,w,av;
    ll id;
    bool operator<(const node &t)const
    {
        return av>t.av;
    }
}arr[N];
inline bool check(double x)
{
    for(int i=1;i<=n;++i)
        arr[i].av=arr[i].v-arr[i].w*x;
    sort(arr+1,arr+1+n);
    double sum=0;
    for(int i=1;i<=k;++i)
        sum+=arr[i].av;
    return sum>=0;
}
void solve()
{
    double l=0,r=mod;
    while(l+EPS<=r)
    {
        double mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else r=mid;
    }
}
int main()
{
    while(~scanf("%lld %lld",&n,&k))
    {
        for(ll i=1;i<=n;++i)
        {
            scanf("%lf %lf",&arr[i].v,&arr[i].w);
            arr[i].id=i;
        }
        solve();
        for(ll i=1;i<=k;++i)
            printf("%lld%s",arr[i].id,i==k?"\n":" ");
    }
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜