Youth的最大化
时间限制：1000 ms | 内存限制：65535 KB
难度：4
描述
Yougth现在有n个物品的重量和价值分别是Wi和Vi，你能帮他从中选出k个物品使得单位重量的价值最大吗？
输入
有多组测试数据
每组测试数据第一行有两个数n和k，接下来一行有n个数Wi和Vi。
(1<=k=n<=10000) (1<=Wi,Vi<=1000000)
输出
输出使得单位价值的最大值。（保留两位小数）
样例输入
3 2
2 2
5 3
2 1
样例输出
0.75
贪心策略：
贪心+二分：
k个物品的最大单位价值 一定大于0且小于单个物品的最大单位价值。求出单个物品的最大单位价值，然后二分查找即可。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define imax(x,y) (x>y?x:y)
#define MAXN 10005
int n, k;
double w[MAXN], v[MAXN];
int i;
double need[MAXN];
int compare(const void * p1, const void * p2) {
return *(double *)p1 < *(double *)p2 ? : -;
}
bool judge(double x) {
// 算出当前物品达到均值x的代价，
//负数表示比均值小，正数反之
for (i = ; i < n; i++) {
need[i] = v[i] - x*w[i];
} //将need数组从大到小排序
qsort(need, n, sizeof(need[]), compare); // 取前k个，算出它们所需代价之和
// 若为正，则代表超过均值，代表均值不够大，向右区间查找；为负反之
double all_need = ;
for (i = ; i < k; i++) {
all_need += need[i];
}
return all_need >= ? true : false;
}
double binary_search(double right) {
double left = ;
while (right - left > 0.00001) {
double mid = (left + right) / ;
if (judge(mid))
left = mid;
else
right = mid;
}
return left;
}
int main(void)
{
while (scanf("%d %d", &n, &k)!=EOF) {
double max_ratio = ;
for (i = ; i < n; i++) {
scanf("%lf %lf", &w[i], &v[i]);
max_ratio = imax(max_ratio,(v[i]/w[i]));
}
//printf("%lf\n", max_ratio);
double res = binary_search(max_ratio);
printf("%.2lf\n", res);
}
return ;
}