题目大意:给定你n个分数,从中找出k个数,使∑a/∑b的最大值
这一题同样的也可以用二分法来做(用DP会超时,可见二分法是多么的实用呵!),大体上是这样子:假设最大的平均值是w,那么题目就是问存不存在∑a/b>=w,我们把这条式子变形
∑a-w∑b>=0
那么这一题就变成了寻找k个最大的a-w*b,使∑a-w∑b>=0成立
#include <iostream>
#include <algorithm>
#include <functional> using namespace std; static double mid, y[];
struct _set
{
int a,b;
}nums[]; bool judge(const int,const int); int main(void)
{
int n, k, t;
double lb, rb; while (~scanf("%d%d", &n, &k))
{
if (n == && k == )
break;
for (int i = ; i < n; i++)
scanf("%d", &nums[i].a);
for (int i = ; i < n; i++)
scanf("%d", &nums[i].b);
lb = ; rb = 1.00, t = ; while (t--)
{
mid = (lb + rb) / ;
if (judge(k, n)) lb = mid;
else rb = mid;
}
printf("%d\n", int( * rb + 0.5));
} return ;
} bool judge(const int k,const int n)
{
double sum = ; for (int i = ; i < n; i++)
y[i] = nums[i].a - nums[i].b*mid;//把∑a/b>=w移项
sort(y, y + n); for (int i = ; i < n - k; i++)
sum += y[n - i - ];//要选择最大的k个,而不是最小的k个
return sum > ;
}