SRM 347 Div1 Medium FlightScheduler

問題

飛行機を使ってdistanceの距離を移動したい。xリットル給油するとの距離を航行できる。それとは別に離陸して高度を得るまでにtakeoffFuelリットル燃料を消費する。着陸した地点で必ず給油できるものとしたとき、distanceの距離を航行するのに必要な燃料の総量を求めよ。

やりかた

一回の給油でゴールまで行くこともできるが、何回か給油したほうが全体では少ない燃料で行ける可能性がある。ただしあまりに着陸＋給油するとtakeoffFuelのコストが大きくなってしまうので適度な回数がいい。このように給油回数に関する必要な燃料の関数を決めるとこの関数は下に凸な関数になっている。この関数の極値を求めればよくそれには三分探索を使用する。

以下ソース。

class FlightScheduler {  
public:
  ll D, _K, em, tf;
  double calc(ll t){ //t回の給油でゴールまで行く時の必要な燃料の総量
    double R = D * 1.0 / t;
    return t * ((exp(R * 1.0 / _K) - 1.0) * em + tf);
  }
  double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel) {
    D = distance; _K = K; em = emptyMass; tf = takeoffFuel;
    ll lb = 1, ub = LLINF;
    while(ub - lb > 10){
      ll x1 = lb + (ub - lb) / 3LL;
      ll x2 = lb + 2LL * (ub - lb) / 3LL;
      if(calc(x2) > calc(x1)) ub = x2;
      else lb = x1;
    }
    double ans = 1e100;
    for(ll i = lb; i <= ub; i++) ans = min(ans, calc(i));
    return ans;
  }
};