长沙理工 ACM 分数规划 1494

题目链接  http://www.acmore.net/problem.php?id=1494

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;

int N,K;
double ai[1123456],bi[1123456],res[1123456],dp[1123456];

bool DO( double mid )
{
    dp[0] = 0; res[0] = 0;
    for( int i = 1; i <= N; i++ )
    {
         dp[i] =  ai[i] - mid*bi[i];
        res[i] = res[i-1] + dp[i];
    }
    for( int i = 1; i <= N; i++ )
        dp[i] = max( dp[i],dp[i-1]+dp[i] );
    for( int i = K; i <= N; i++ )
    if( res[i] - res[i-K] + max( 0.,dp[i-K] ) >= 0 )
     return true;
    return false;
}
double search( double lt,double rt )
{
    while( rt - lt > 0.00000001 )
    {
        double mid = ( lt + rt )/2.;
        if( DO(mid) ) lt = mid;
        else          rt = mid;
    }
    return lt;
}
int main( )
{
    while( scanf("%d%d",&N,&K) != EOF )
    {
        for( int i = 1; i <= N; i++ )
           scanf("%lf",&ai[i]);
        for( int j = 1; j <= N; j++ )
           scanf("%lf",&bi[j]);
        printf("%.4lf\n",search(0,1000));
    }
    return 0;
}