WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM676 Div1 Easy "WaterTank"

解法

outputの秒間流量を決め打って、溢れる溢れないを判定。それをにぶたん。

事後

誤差について理解できてないのでこういう問題怖い

ソースコード

int C;
vector<int> T;
vector<int> X;
int N;
class WaterTank {
    public:
    double minOutputRate(vector<int> t, vector<int> x, int c) {
        T = t;
        X = x;
        C = c;
        N = t.size();

        double L = 0.0;
        double R = 1e9;
        for (int i = 0; i < 50; i++) {
            double m = (L + R) / 2;
            if (solve(m)) {
                R = m;
            } else {
                L = m;
            }
        }

        return L;
    }

    bool solve(double output) {
        double S = 0.0;
        for (int i = 0; i < N; i++) {
            double inc = (double)X[i] * T[i];
            double dec = output * T[i];
            S = max(0.0, S + inc - dec);
            if (S > C) {
                return false;
            }
        }
        return true;
    }
};