解を仮定し可能か判定

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;         // 短くすべきか
}