search

dak2 / algorithms

This repository stores my solutions to competition programming questions and implementations of algorithms.
0 stars 0 forks source link

001 - Yokan Party #19

Closed dak2 closed 5 months ago

dak2 commented 5 months ago

https://atcoder.jp/contests/typical90/tasks/typical90_a

dak2 commented 5 months ago

切れ目の入ったようかん切った場合のピースの長さを全てx以上とすることができるかどうかの判定

二分探索法を使って、切れ目に沿って切った全てのピースが中央値以上になるどうかを確認し、そのピースの数がK+1個以上であるかどうかを判定

trueであれば範囲の始端（左値）を中央値、falseであれば終端（右値）を中央値にセットし、始端と終端の差が1になるまで確認する

差分が1になったら最小値なので始端の値が答えになる