01分数规划——POJ2976
发布时间：2020-12-14 05:10:35 所属栏目：大数据 来源：网络整理
导读：题目链接 题目含义 去掉k个测试，让sigmaAi / sigmaBi最大 题目分析 若sigmaAi/sigmaBi取得最大 那么任意去除k个成绩，取得的答案ans=sigmaAi/sigmaBi 转换一下就是 sigmaAi-sigmaBi*ans=0 再转换一下就是 sigma( Ai-Bi*ans ?)=0 对于ans我们用二分来求，如
|
题目链接 题目含义 去掉k个测试，让sigmaAi / sigmaBi最大 题目分析 若sigmaAi/sigmaBi取得最大 那么任意去除k个成绩，取得的答案ans<=sigmaAi/sigmaBi 转换一下就是 sigmaAi-sigmaBi*ans>=0 再转换一下就是 sigma( Ai-Bi*ans ?)>=0 对于ans我们用二分来求，如果 这个式子>=0 ?ans满足，去找更大的ans满不满足 如果<0，ans不满足，就去找满足的最大的ans 题目代码 #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int maxn=1007; const double eps=1e-7; double a[maxn],b[maxn],p[maxn]; int n,k; int main(){ while(scanf("%d%d",&n,&k)){ if(n==0&&k==0)break; for(int i=1;i<=n;i++) scanf("%lf",&a[i]); for(int i=1;i<=n;i++) scanf("%lf",&b[i]); double l=0.0,r=1.0,mid; while(r-l>eps){ mid=(l+r)/2; for(int i=1;i<=n;i++) p[i]=a[i]-b[i]*mid; sort(p+1,p+1+n); double sum=0; for(int i=k+1;i<=n;i++) sum+=p[i]; if(sum>=0)l=mid; else r=mid; } printf("%.0fn",mid*100); } return 0; } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |