Youth的最大化

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <stdbool.h>
 4 #define imax(x,y) (x>y?x:y)
 5 #define MAXN 10005
 6 int n, k;
 7 double w[MAXN], v[MAXN];
 8 int i;
 9 double need[MAXN];
10 int compare(const void * p1, const void * p2) {
11     return *(double *)p1 < *(double *)p2 ? 1 : -1;
12 }
13 bool judge(double x) {
14     // 算出当前物品达到均值x的代价，
15     //负数表示比均值小，正数反之
16     for (i = 0; i < n; i++) {
17         need[i] = v[i] - x*w[i];
18     }
19 
20     //将need数组从大到小排序
21     qsort(need, n, sizeof(need[0]), compare);
22 
23     // 取前k个，算出它们所需代价之和
24     // 若为正，则代表超过均值，代表均值不够大，向右区间查找；为负反之
25     double all_need = 0;
26     for (i = 0; i < k; i++) {
27         all_need += need[i];
28     }
29     return all_need >= 0 ? true : false;
30 }
31 double binary_search(double right) {
32     double left = 0;
33     while (right - left > 0.00001) {
34         double mid = (left + right) / 2;
35         if (judge(mid))
36             left = mid;
37         else
38             right = mid;
39     }
40     return left;
41 }
42 int main(void)
43 {
44     while (scanf("%d %d", &n, &k)!=EOF) {
45         double max_ratio = 0;
46         for (i = 0; i < n; i++) {
47             scanf("%lf %lf", &w[i], &v[i]);
48             max_ratio = imax(max_ratio,(v[i]/w[i]));
49         }
50         //printf("%lf\n", max_ratio);
51         double res = binary_search(max_ratio);
52         printf("%.2lf\n", res);
53     }
54     return 0;
55 }