山东省第八届acm省赛E题 三分+二分

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double eps=2*1e-8;
int a[5005],b[5005],k,n,m;
double res[5005],ans,f[1000005];
inline bool cmp(double a,double b)
{
    return a>b;
}
inline bool check(double kp,int c)
{
    for(int i=0;i<n;i++)
        res[i]=(a[i]+c)%m-kp*b[i];
    sort(res,res+n,cmp);
    double ans=0.0;
    for(int i=0;i<k;i++)
        ans+=res[i];
    if(ans>=0)
        return true;
    else
        return false;
}
inline double cal(int k)
{
    if(f[k]>0)
        return f[k];
    double l=0.0,r=m,mid;
    int cnt=0;
    while(r-l>eps)
    {
        cnt++;
        mid=(r+l)/2;
        if(check(mid,k))
            l=mid;
        else
            r=mid;
    }
    return f[k]=mid;
}
int main()
{
    while(scanf("%d%d%d",&n,&k,&m)!=EOF)
    {
        memset(f,0,sizeof(f));
        for(int i=0;i<n;i++)
            scanf("%d",a+i);
        for(int i=0;i<n;i++)
            scanf("%d",b+i);
        ans=0.0;
        int sl=0,sr=m-1,ll,rr;
        while(sl+1<sr)
        {
            int rr=(sl+2*sr)/3.0+0.5,ll=(sl*2+sr)/3.0+0.5;
            if(cal(ll)>cal(rr))
                sr=rr;
            else
                sl=ll;
        }
        printf("%.7f\n",max(f[sr],f[sl]));
    }
    return 0;
}