Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:提供ac代码In Reply To:提供ac代码 Posted by:a1b3c7d9 at 2019-05-01 17:15:59 > 这题真的卡精度,耗了一个下午,感谢lyd,顺便提供ac代码,以便后人 > > #include <iostream> > #include <cstdio> > #include <algorithm> > #define il inline > #define ri register > #define db double > #define exact 0.00000001 > int n,k;db a[2001],b[2001],c[2001]; > using namespace std; > il bool check(db); > il db dfs(db,db); > int main(){ > int i,j; > while(scanf("%d%d",&n,&k),n||k){ > for(i=1;i<=n;++i)scanf("%lf",&a[i]); > for(i=1;i<=n;++i)scanf("%lf",&b[i]); > printf("%0.f\n",dfs(0,1)); > } > return 0; > } > il bool check(db s){ > int i;db j(0); > for(i=1;i<=n;++i)c[i]=a[i]-s*b[i]; > sort(c+1,c+n+1);for(i=k+1;i<=n;++i)j+=c[i]; > if(j>exact)return true;return false; > } > il db dfs(db l,db r){ > db mid; > while(r-l>exact){ > mid=(l+r)/2; > if(check(mid))l=mid+exact; > else r=mid-exact; > }return (l+r)*50; > } #include <iostream> #include <cstdio> #include <algorithm> #define il inline #define ri register #define db double #define exact 0.00000001 using namespace std; struct save{ db data;int id; il bool operator<(const save&x){ return data<x.data; } }c[2001]; db a[2001],b[2001]; int main(){ int n,k,i;db l,mom,son; while(scanf("%d%d",&n,&k),n||k){ for(i=1;i<=n;++i)scanf("%lf",&a[i]); for(i=1;i<=n;++i)scanf("%lf",&b[i]); l=0;while(true){ for(i=1;i<=n;++i)c[i].data=a[i]-b[i]*l,c[i].id=i; sort(c+1,c+n+1),mom=0,son=0; for(i=k+1;i<=n;++i)son+=a[c[i].id],mom+=b[c[i].id]; if(son/mom-l>exact)l=son/mom; else break; }printf("%.0f\n",l*100); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator