SRM 676 div1 easy: WaterTank

SRM 676 には寝坊したので不参加です。easy 楽勝だったので出ればレート上がったよな…

問題

TopCoder Statistics - Problem Statement

解法

R について二分探索すれば良いです。簡単すぎない？

bool ok(double R, const vi& t, const vi& x, int C) {
    int n = t.size();
    double now = 0;
    for (int i = 0; i < n; i++) {
        now += (x[i]-R)*t[i];
        now = max<double>(now, 0);
        if (now > C) return false;
    }
    return true;
}

class WaterTank {
public:
    double minOutputRate(vector <int> t, vector <int> x, int C) {
        double low = 0, high = 1e6;
        for (int i = 0; i < 100; i++) {
            double med = (high+low)/2;
            if (ok(med, t, x, C)) high = med;
            else low = med;
        }
        return high;
    }
};