Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator