解を仮定し可能か判定
L_iの紐N本から同じ長さの紐をK本切り出したときの最長の長さを求めよ。
評価関数:C(x) = xでK本以上切り出せるか
<=> C(x) = floor(L_i/x)の総和がK以上
bool C(double x) { int num = 0; for(int i=0; i<N; i++) num += (int)(L[i] / x); return num >= K; // >=であれば、少なくともK本は切り出せる }
後は上の評価関数を用いて二分探索する。100回くらい探索すれば解として十分な精度が得られる。
int lb = 0, ub = INF; for(int i=0; i<100; i++) { double mid = (lb + ub) / 2; if(C(mid)) lb = mid; // もっと長く切り出せるか else ub = mid; // 短くすべきか }