きままにものづくり

日々の気付いたことなんかを書いてます。

SRM613Div1Easy

問題

N個の数列が与えられる。各要素は+Xか-Xだけ移動しなければならない。数列の最小と最大の要素の差の最小値を求めよ。

解法

数列をソートする。
小さい順から適応していくと、+Xをする要素と-Xをする要素の2つに分解できる。+Xをした後に-Xをし、また+Xをするということはない。境目を線形探索で見つければ答えが求まる。(+++---+となることはなく、必ず++++-----といったようになる。)
簡単な証明をする。+Xをするのが最適なi番目の要素と-Xをするのが最適なj番目の要素を考える。iとjは隣合っているとする。iよりも小さい要素kを-X方向に動かす。これは、jよりも-方向に大きな値になるのでjを-方向に動かすのは最適ではない。jよりも大きい要素であるtに関しても同様のことがいえる。よって、ふたつの要素に分解可能になる。

計算量

ソート:  O(N logN)
探索:  O(N)

コード

広告を非表示にする