poj2976 发表于 2018-11-01 | 分类于 题解 | 阅读数 次 链接:poj2976 题解 裸题,注意精度 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e3+7;const ll lnf=0x3f3f3f3;const double esp=1e-3;double a[N],b[N],c[N];int n,m;double check(double x){ double ans=0; rep(i,1,n)c[i]=1ll*a[i]-1ll*x*b[i]; sort(c+1,c+n+1); repd(i,n,m+1){ ans+=c[i]; if(ans<0)return -1; } return ans;}double find(){ double l=0,r=1.0*lnf; while(l+esp<r){ double mid=(l+r)/2; if(check(mid)>=0)l=mid; else r=mid; } return l;}int main(){ while(~scanf("%d%d",&n,&m)&&(n||m)){ rep(i,1,n){scanf("%lf",&a[i]);a[i]*=100;} rep(i,1,n)scanf("%lf",&b[i]); double ans=find(); printf("%.0f\n",ans); } return 0;} Dinkelbach算法 123456789101112131415161718192021222324252627282930313233343536373839404142#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e3+7;const ll lnf=0x3f3f3f3;const double esp=1e-3;struct node{ double a,b,c; inline double f(double x){c=a-b*x;}}a[N];int n,m;inline int cmp(node x,node y){return x.c<y.c;}double solve(double x){ rep(i,1,n)a[i].f(x); sort(a+1,a+n+1,cmp); double aa=0,bb=0; repd(i,n,m+1){aa+=a[i].a;bb+=a[i].b;} return aa/bb;}double find(){ double l=0,r=solve(0); while(l+esp<r){ l=r;r=solve(r); } return l;}int main(){ while(~scanf("%d%d",&n,&m)&&(n||m)){ rep(i,1,n){scanf("%lf",&a[i].a);a[i].a*=100;} rep(i,1,n)scanf("%lf",&a[i].b); double ans=find(); printf("%.0f\n",ans); } return 0;}