Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:提供ac代码

Posted by a1b3c7d9 at 2019-05-01 17:34:11 on Problem 2976
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: