最大化平均值---二分搜索

有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)。

代碼：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn=1e4;
const double eps=1e-5;
int w[maxn],v[maxn],n,k;
double y[maxn];
bool check(double r)
{
	for(int i=0;i<n;i++){
		y[i]=v[i]-r*w[i];
	}
	sort(y,y+n);
	reverse(y,y+n);
	double sum=0;
	for(int i=0;i<k;i++)
	{
		sum+=y[i];
	}
	return sum>=0;
} 
int main()
{
	while(cin>>n)
	{
		cin>>k;
		for(int i=0;i<n;i++)
			cin>>w[i]>>v[i];
		double lb=0,ub=1e6;
		while(ub-lb>eps)
		{
			double mid=(lb+ub)/2;
			if(check(mid)) lb=mid;
			else ub=mid;
		}
		printf("%.2f\n",ub);	 
	}
	return 0;
}