nyoj914 Yougth的最大化

/*
  这题其实并不难，背包问题，属于动态规划中的简单题
  以及，后来发现有个blog上，做了不错的优化
  http://www.cnblogs.com/wd-one/p/4480433.html
  
  在输入w、v数组时，同时可以计算出所有输入数据中，得到的最大的单位质量的价值，于是这个才应该作为二分查找的最大值，而不是我所用的INF，从INF要二分到最终所得的平均价值，还是麻烦不少的，虽然二分本身效率的确高，但是，能精确化边界，精确平均价值的上界，总会更完美些
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
const int INF = 0x3f3f3f3f;
const int MAX_N = 10010;
using namespace std;

int n, k;
int w[MAX_N], v[MAX_N];

double y[MAX_N]; // v - x * w

// 判断是否满足条件
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;
	// 计算y数组中从大到小前k个数的和
	for (int i = 0; i < k; i++)
	sum += y[n - 1 - i];
	
	return sum >= 0; 	 
} 
void solve()
{
	double lb = 0, ub = INF;
	for (int i = 0; i < 100; i++)
	{
		double mid = (lb + ub) / 2;
		if (C(mid)) lb = mid;
		else ub = mid;
	}
	printf("%.2f
", lb);
}

int main()
{
	while (cin >> n >> k)
	{
		for (int i = 0; i < n; i++) cin >> w[i] >> v[i]; 
		solve();
	}
	return 0;
}