TopCoder SRM 347 Div1 Medium FlightScheduler

問題

燃料が空の時の質量がempty mass,離陸時に燃料を積んだ状態での質量がtake-off massであるような飛行機はKを定数として、
R = K * ln(take-off mass / empty mass)
の距離だけ飛行できる。

distanceの距離を飛行機が飛ぶには最低でどれだけの燃料が必要か。
飛行機は、航空途中に好きな位置で着陸して給油することができる。
ただし、一回離陸するたびに、takeoffFuelだけ余分な燃料が必要となるものとする。

制約条件

distance≦200000
K≦200000
emptyMass≦200000
takeoffFuel≦200000

方針

n回途中で着陸するとき、着陸地点は、スタートとゴールを(n+1)等分した地点とするのが最適。
離陸回数をn回（最初の1回+途中の着陸回数）と決めると、
必要な燃料の量は求まる。

nについて三分探索すると、最適な着陸回数のnが求まる。

ソースコード

class FlightScheduler {
	public:
	double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel) 
	{
		#define calc(x) (exp(distance*1.0/x/K)*emptyMass+takeoffFuel-emptyMass)*x
		ll lo=1,hi=1ll<<60,l,r;
		rep(i,100){
			l=(lo*2+hi)/3;
			r=(lo+hi*2)/3;
			double f1=calc(l), f2=calc(r);
			if(f1<f2)hi=r; else lo=l;
		}
		double ans=INF;
		for(ll i=lo;i<=hi;i++)ans=min(ans,calc(i));
		return ans;
	}
};