http://acdream.info/onecontest/1044#problem-H

观察到:对于的路,是一定要耗油的,所以这样「处理」之后,每km的耗油量与v成正比。
因此,对于的相邻两段路,可以将之合并成一段路,这个思想是解决这道题的关键所在。

但是由于以及max(0,0.5*v+bi)的存在,我们必须二分速度,且对于0.5*v+bi<=0的段,我们必须「全速」地跑。

/*1712 ms, 3240 KB*/
const double eps = 1e-8;
const int mx = int(1e5) + 5;

int n;
double ans, f, vm, s[mx], b[mx];

bool ok(double v)
{
    int i;
    double tmp, cost = 0.0, t = 0.0;
    For(i, n)
    {
        tmp = 0.5 * v + b[i];
        if (tmp > eps)
        {
            cost += tmp * s[i], t += s[i] / v;
            if (cost > f + eps) return false;
        }
        else t += s[i] / min(vm, -2 * b[i]);
    }
    return ans = t, true;
}

void solve(double l, double r)
{
    double m;
    int i;
    For(i, 100) /// 最好可以开到32
    {
        m = (l + r) / 2;
        ok(m) ? l = m : r = m;
    }
}

int main()
{
    int i;
    while (~SI(n))
    {
        SDD(f, vm);
        For(i, n) SDD(s[i], b[i]);
        ans = 1e100;
        solve(0, vm + eps);
        ans == 1e100 ? puts("Bad Luck!") : PD(ans);
    }
    return 0;
}

Comments

comments powered by Disqus