POJ 3111 K Best(最大化平均值)

迷南。 2022-02-01 01:31 151阅读 0赞

**题目链接** ： [click here~~][click here]

【**题目大意**】有n个物品的重量和价值各自是Wi和Vi。从中选出K个物品使得单位重量的价值最大，输出物品的编号

【**解题思路**】：最大化平均值的经典.參见[click here~~][click here 1]

代码：

//#include <bits/stdc++.h>
    #include <stdio.h>
    #include <math.h>
    #include <string.h>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int N=1e5+10;
    const double eps=1e-8;
    int n,k,m;
    struct node
    {
        double y,v,w;//价值。重量
        int id;
    }pp[N];
    bool cmp(node a,node b)
    {
        return a.y>b.y;
    }
    bool get(double mid)//能够选择使得单位重量的价值不小于mid
    {
        bool pk;
        for(int i=0; i<n; i++) pp[i].y=pp[i].v-mid*pp[i].w;
        sort(pp,pp+n,cmp);   //从大到小排序
        double sum=0;
        for(int i=0; i<k; i++)
            sum+=pp[i].y;//从大往小选择
        if(sum>=0) pk=true;
        else pk=false;
        return pk;
    }
    int main()
    {
        //freopen("1.txt","r",stdin);
        scanf("%d%d",&n,&k);
        for(int i=0; i<n; i++){
            scanf("%lf%lf",&pp[i].v,&pp[i].w);
            pp[i].id=i+1;
        }
        double ll=0,rr=1e8;
        while(fabs(ll-rr)>eps)
        {
            double mid=(ll+rr)/2;
            if(get(mid)) ll=mid;
            else rr=mid;
        }
        //printf("%.2f\n",rr);
        printf("%d",pp[0].id);
        for(int i=1;i<k;i++)
        printf(" %d",pp[i].id);
        puts("");
    }

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5208042.html，如需转载请自行联系原作者

[click here]: http://poj.org/problem?id=3111
[click here 1]: http://blog.csdn.net/u013050857/article/details/46363001