SRM598Div1Easy
問題
サイズNの数列が与えられる。300の値を格納できる箱がある。与えられた数列の全ての要素を箱に格納するのに必要な箱の数の最小値を求めよ。
解法
少し、制限を設けた貪欲法で解ける。
数列を昇順にソートし、左側(小さい値)と右側(大きい値)を足し合わせ300以下なら、2つを箱に入れ、300以上なら右側の要素を箱に入れる。初めの要素に100が連続する場合は、3つおきに始点を変更し、同様の方法を行う。これにより、最小値が求まる。
計算量
サイズNの数列が与えられる。300の値を格納できる箱がある。与えられた数列の全ての要素を箱に格納するのに必要な箱の数の最小値を求めよ。
少し、制限を設けた貪欲法で解ける。
数列を昇順にソートし、左側(小さい値)と右側(大きい値)を足し合わせ300以下なら、2つを箱に入れ、300以上なら右側の要素を箱に入れる。初めの要素に100が連続する場合は、3つおきに始点を変更し、同様の方法を行う。これにより、最小値が求まる。