TopCoder SRM 676 Div1 Easy: WaterTank

,

[Easy: WaterTank]()

解説

単に二分探索すればよい。$O(n \log x)$。

タンクの水量の変化は、タンクに入る水の量の変化する時点(とタンクが空になる時点)を頂点とした折れ線グラフになるので、単にその頂点で限界$C$を越えているかのみを見ればよい。

実装

#include <bits/stdc++.h>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
class WaterTank {
public:
    double minOutputRate(vector<int> t, vector<int> x, int C) {
        int n = t.size();
        double l = 0, r = *max_element(x.begin(), x.end());
        while (r - l > 1e-8) {
            double m = (l + r) / 2;
            bool ok = true;
            double water = 0;
            repeat (i,n) {
                water += t[i] * (x[i] - m);
                water = max(0.0, water);
                if (C < water) {
                    ok = false;
                    break;
                }
            }
            (ok ? r : l) = m;
        }
        return l;
    }
};