POJ2976 Dropping tests（01分数规划）

题目大概说给n个二元组Ai和Bi，要去掉k个，求余下的100*∑Ai/∑Bi的最大值。

假设要的最大的值是ans，令Di=Ai-ans*∑Bi，对Di排序取最大的n-k个，如果∑Ai-ans*∑Bi>0，说明ans还可以更大，反之ans太大了，所以二分枚举一下ans判断即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 1111
 7 #define eps 1e-9
 8 
 9 int n,k;
10 double a[MAXN],b[MAXN],d[MAXN];
11 double calc(double L){
12     for(int i=0; i<n; ++i){
13         d[i]=a[i]-L*b[i];
14     }
15     sort(d,d+n);
16     double res=0;
17     for(int i=0; i<k; ++i){
18         res+=d[n-i-1];
19     }
20     return res;
21 }
22 
23 int main(){
24     while(~scanf("%d%d",&n,&k) && (n||k)){
25         k=n-k;
26         for(int i=0; i<n; ++i){
27             scanf("%lf",a+i);
28         }
29         for(int i=0; i<n; ++i){
30             scanf("%lf",b+i);
31         }
32         double l=0,r=1,ans;
33         while(fabs(l-r)>eps){
34             ans=(l+r)/2;
35             if(calc(ans)>0) l=ans;
36             else r=ans;
37         }
38         printf("%.0f
",ans*100);
39     }
40     return 0;
41 }