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