欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ 3111 K Best (最大化平均值,贪心 二分)难度⭐⭐

程序员文章站 2022-06-03 13:38:37
...

题目来源:
【题意】
有n个物品的重量和价值分别是wi,vi,从中选取k个物品使得单位重量的价值最大。
输出格式:
输出一行物品的编号。
POJ 3111 K Best (最大化平均值,贪心 二分)难度⭐⭐

#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;
}

有任何疑问欢迎评论哦虽然我真的很菜
点个关注再走吧