POJ 2976 Dropping tests【二分最大化平均值】

题意：定义最大平均分为（a1+a2+a3+---+an）/（b1+b2+---+bn），求任意去除k场考试的最大平均成绩

和挑战程序设计上面的最大化平均值的例子一样

判断是否存在x满足条件（a1+a2+a3+---+an）/（b1+b2+---+bn）>=x

把这个不等式变形就得到

E(ai-x*bi )>=0

所以可以对ai-x*bi降序排序，取前n-k个，看它们的和是不是>=0(或者升序排，取后n-k个)

后来搜题解发现是01分数规划，列的式子好像都差不多-------

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=10005;
17 
18 double a[maxn],b[maxn],y[maxn];
19 int n,k;
20 
21 
22 int ok( double x){
23     for(int i=1;i<=n;i++) y[i]= a[i]-b[i]*x;
24     sort(y+1,y+n+1);
25     double ans=0;
26     for(int i= k+1;i<=n;i++) ans+=y[i];
27     
28     return ans>=0;
29 }
30 
31 int main(){
32     while(scanf("%d %d",&n,&k)!=EOF){
33         if(n==0&&k==0) break;
34         for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
35         for(int i=1;i<=n;i++) scanf("%lf",&b[i]);
36         
37         double lb=0,ub=1.00,mid;
38         for(int i=0;i< 100;i++){
39             mid=(lb+ub)/2;
40             if(ok(mid)) lb=mid;
41             else ub=mid;
42         }
43         printf("%d
",(int)(100*lb+0.5));
44     }
45     return 0;
46 }

View Code

好饿~~(╯﹏╰)b

加油啊---------------goooooooooo----------

POJ 2976 Dropping tests【二分 最大化平均值】

POJ 2976 Dropping tests【二分最大化平均值】