POJ 2976 Dropping tests：01分数规划【二分】

题目链接：http://poj.org/problem?id=2976

题意：

　　共有n场考试，每场考试你得的分数为a[i]，总分为b[i]。

　　你可以任意去掉k场考试。

　　问你最大的 100.0 * ( ∑ a[i] / ∑ b[i] )的值。（四舍五入）

题解：

　　相当于从n场考试中选n-k场。

　　二分：

　　　　二分最大答案 ∑ a[i] / ∑ b[i] >= L

　　　　即：∑ a[i] - ∑(b[i]*L) >= 0

　　check函数：

　　　　求数组val[i] = a[i] - b[i]*L

　　　　将val排序。

　　　　取最大的n-k个val[i]，求和为sum。

　　　　若sum >= 0则满足条件，lef = mid.

　　　　否则rig = mid.

AC Code:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #define MAX_N 1005
 6 #define INF 10000000
 7 #define EPS 0.000001
 8 
 9 using namespace std;
10 
11 int n,m;
12 double ans;
13 double a[MAX_N];
14 double b[MAX_N];
15 double val[MAX_N];
16 
17 void read()
18 {
19     for(int i=0;i<n;i++)
20     {
21         scanf("%lf",&a[i]);
22     }
23     for(int i=0;i<n;i++)
24     {
25         scanf("%lf",&b[i]);
26     }
27 }
28 
29 bool is_legal(double x)
30 {
31     for(int i=0;i<n;i++)
32     {
33         val[i]=a[i]-x*b[i];
34     }
35     sort(val,val+n);
36     double sum=0;
37     for(int i=n-1;i>=m;i--)
38     {
39         sum+=val[i];
40     }
41     return sum>=0;
42 }
43 
44 void solve()
45 {
46     double lef=0;
47     double rig=1;
48     while(rig-lef>EPS)
49     {
50         double mid=(lef+rig)/2.0;
51         if(is_legal(mid)) lef=mid;
52         else rig=mid;
53     }
54     ans=lef;
55 }
56 
57 void print()
58 {
59     printf("%.0f
",ans*100.0);
60 }
61 
62 int main()
63 {
64     while(scanf("%d%d",&n,&m)!=EOF)
65     {
66         if(n==0 && m==0) break;
67         read();
68         solve();
69         print();
70     }
71 }