最大化平均值---二分搜索 - R_xiaozhu_Q的专栏 - 博客频道 - CSDN.NET

有n个物品的重量和价值分别是w[i]和v[i]，从中选出K个物品使得单位重量的价值最大。
1<=k<=n<=10^4
1<=w[i],v[i]<=10^6
一般想到的是按单位价值对物品排序，然后贪心选取，但是这个方法是错误的，对于有样例不满足。我们一般用二分搜索来做（其实这就是一个01分数规划）
我们定义：
条件 C(x) :=可以选k个物品使得单位重量的价值不小于x。
因此原问题转换成了求解满足条件C(x)的最大x。那么怎么判断C(x)是否满足？
变形：（sigma(v[i])/sigma(w[i])）>=x (i 属于我们选择的某个物品集合S)
进一步：sigma(v[i]-x*w[i])>=0
于是：条件满足等价于选最大的k个和不小于0.于是排序贪心选择可以判断，每次判断的复杂度是O(nlogn)。

1. const double eps=1e-5;  
2. int w[maxn],v[maxn],n,k;  
3. double y[maxn];  
4. bool check(double r)  
5. {  
6.     for(int i=0;i<n;i++){  
7.         y[i]=v[i]-r*w[i];  
8.     }  
9.     sort(y,y+n);  
10.     reverse(y,y+n);  
11.     double sum=0;  
12.     for(int i=0;i<k;i++)  
13.     {  
14.         sum+=y[i];  
15.     }  
16.     return sum>=0;  
17. }   
18. int main()  
19. {  
20.     while(cin>>n)  
21.     {  
22.         cin>>k;  
23.         for(int i=0;i<n;i++)  
24.             cin>>w[i]>>v[i];  
25.         double lb=0,ub=1e6;  
26.         while(ub-lb>eps)  
27.         {  
28.             double mid=(lb+ub)/2;  
29.             if(check(mid)) lb=mid;  
30.             else ub=mid;  
31.         }  
32.         printf("%.2f\n",ub);       
33.     }  
34.     return 0;  
35. }

Read full article from 最大化平均值---二分搜索 - R_xiaozhu_Q的专栏 - 博客频道 - CSDN.NET