SRM629Div1Easy
問題
横幅がW、縦幅がHの四角形の穴があり、それを埋めるための四角形の板がN個()与えれる。穴を埋めるの最小な板の数を求めよ。
ただし、以下の条件を満たさなければならない。
- 板の四隅は穴の外側(板の横幅か縦幅のどちらかが穴の横幅か縦幅より真に大きい)
- 穴の辺と板の辺は平行(板の横幅と縦幅の値は交換可能)
解法
貪欲法で解くことができる。
横幅か縦幅の片方をしきい値とし、板をフィルタリングする。結果を降順にソートし、しきい値として選ばなかった方の値以上になる点を見つければ良い。どちらをしきい値にするかで最小値は変わるので両方を求めて小さい方を出力すれば良い。
計算量
ソート: O(N log N)
メイン: O(N)
N:
