| ||||||||||
| 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