[POJ2976]Dropping tests（01分数规划）

2019-11-08 19:44:09

字体：大中小

来源：转载

供稿：网友

题目描述

传送门题意：给出ai,bi，选择至少n-k个，使100*∑ai∑bi $/sum a_i/over/sum b_i$ 最大

题解

01分数规划裸题… 化一下式子R=∑ai∑bi $R={/sum a_i/over/sum b_i}$ ，那么当di=∑ai−R∗∑bi>0 $d_i=/sum a_i-R*/sum b_i>0$ 的时候一定存在更优解二分R，算出di $d_i$ ，贪心地选前n-k大，然后判断是否存在更优解就可以了

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 1005const double eps=1e-4;int dcmp(double x){ if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1;}int n,k;double a[N],b[N],d[N],ans;bool check(double mid){ for (int i=1;i<=n;++i) d[i]=a[i]-mid*b[i]; sort(d+1,d+n+1); double now=0; for (int i=n;i>k;--i) now+=d[i]; return dcmp(now)>=0;}double find(){ double l=0.0,r=1.0,mid,ans; while (dcmp(r-l)>0) { mid=(l+r)/2.0; if (check(mid)) ans=l=mid; else r=mid; } return ans;}int main(){ while (~scanf("%d%d",&n,&k)) { if (!n&&!k) break; for (int i=1;i<=n;++i) scanf("%lf",&a[i]); for (int i=1;i<=n;++i) scanf("%lf",&b[i]); ans=100.0*find(); PRintf("%.0lf/n",ans); }}

上一篇：[POJ2728]Desert King（01分数规划）

下一篇：如何用servlet写网页访问量计数器？