Yougth现在有n个物品的重量和价值分别是Wi和Vi,你能帮他从中选出k个物品使得单位重量的价值最大吗?
3 2 2 2 5 3 2 1
0.75
思路:二分加贪心#include<stdio.h> #include<iostream> #include<algorithm> using namespace std; int w[10000],v[10000],n,k; double y[10000]; bool C(double x) { for(int i=0;i<n;i++) { y[i]=v[i]-x*w[i]; } sort(y,y+n); double sum = 0; for(int i=0;i<k;i++) { sum+=y[n-i-1]; } return sum>=0; } void solve() { double lb =0,ub=10000; for(int i=0;i<100;i++) { double mid =(lb+ub)/2; if(C(mid)) lb = mid; else ub=mid; } printf("%.2f\n",ub); } int main() { while(cin>>n>>k) { for(int i=0;i<n;i++) cin>>w[i]>>v[i]; solve(); //system("pause"); } return 0; }
NYOJ 914 Yougth的最大化,布布扣,bubuko.com
原文:http://blog.csdn.net/an327104/article/details/26006987