最大化を二分探索で

• $\max_x f(x)$ を $f(x) > X$を満たす解の存在判定問題にしてXを二分探索する
• xが順列や部分集合などで全探索不可能なサイズ
• max f(x)を求める貪欲アルゴリズムが思いつかない時、f(x)>Xを満たす解の存在判定にすると、最大の解に限らず見つければ良いのでやりやすくなる

「答えを決め打つ」タイプの二分探索を使いこなそう - ARMERIA 最大化は二分探索

和の比率の最大化