AOJ 2592 Flowers

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2592

解法

3分探索．（自分は黄金比探索を持ってたのでそれを貼り付けた．）
使う水の量が決まれば，使う肥料の量は一位に定まる．つまり，コスト関数はWのみを引数とする関数である．
グラフをイメージしてみると，このグラフは（滑らかではないが）下に凸な関数であることがわかるので，3分探索すれば解が求まる．

3分探索でなくとも，明らかにLPの形をしてるので，双対を取ってやるのもよさそうではある．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr double eps = 1e-8;
constexpr double gratio = (std::sqrt(5)+1)/2.0;

template <typename F>
double golden_section_search(F f, double lb, double ub, int cnt) {
    double x1 = (ub-lb)/(gratio+1) + lb,
           x2 = (ub-lb)*gratio/(gratio+1) + lb;
    double v1 = f(x1), v2 = f(x2);
    for(int i=0; i<cnt; ++i) {
        if(v1 < v2) {
            ub = x2;
            x2 = x1;
            v2 = v1;
            x1 = (ub-lb)/(gratio+1) + lb;
            v1 = f(x1);
        } else {
            lb = x1;
            x1 = x2;
            v1 = v2;
            x2 = (ub-lb)*gratio/(gratio+1) + lb;
            v2 = f(x2);
        }
    }
    return (lb+ub)/2;
}

int main() {
    int N;
    while(cin >> N, N) {
        double pw;
        cin >> pw;
        vector<double> vw(N), pf(N), vf(N), th(N);
        double res = 0;
        for(int i=0; i<N; ++i) {
            cin >> vw[i] >> pf[i] >> vf[i] >> th[i];
            res += max(0.0, th[i] / vf[i] * pf[i]);
        }
        auto f = [&](double W) {
            double cost = W * pw;
            for(int i=0; i<N; ++i) {
                cost += max(0.0, (th[i] - vw[i] * W) / vf[i] * pf[i]);
            }
            return cost;
        };
        cout << fixed << setprecision(10) << f(golden_section_search(f, 0, 1e9, 300)) << endl;
    }
}