AOJ 2592 Flowers
解法
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; } }