ABC013 C - 節制

C - 節制
提出コード
数学に強い系か、実装のほうができる系によって解き方がかわる面白い問題です(これに限らず時々おこりますが...)
素直に全探索について考えてみます。
普通の食事をi日、質素な食事をj日、食べない日をk日として3重ループすると、間に合わず、さらに食べない日をN-i-j日として2重ループまで計算量を落としてもまだ間に合いません。
ということで、あたりまで間に合わないので、1重ループで何かうまいこと調べる方法を探ります。
すると、二分探索がうまく機能しそうだな、ということに気づきます。
普通の食事をi日食べると決めうったときに、質素な食事をとる日数のうち一番少なくて済むものを、二分探索で求めます。
あとは、lとrを初期値が0、N-iとなるようにして、二分探索していいきましょう。
iを全探索して、一番最小の費用を求めたらそれが答えになります。
数学に強い人はで求められるみたいですね。