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

本文主要是介绍POJ 3111 K Best(最大化平均值)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接： click here~~

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

【解题思路】：最大化平均值的经典.参见click here~~

代码：

//#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("");
}

这篇关于POJ 3111 K Best(最大化平均值)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---