問題
数列要素の組み合わせによる差の最小化
本問題の場合、入力を受けた長さが等しく$N$である2数列のそれぞれの要素の差を、重複なしでN個とってきたときの差の合計値の最小化をいかにして求めるか、について以下の原理を導くことが難しい。
原理
長さが等しく$N$である2数列のそれぞれの要素の差を重複なしでN個とってきたときの差の合計値minは
2数列をそれぞれソートしたものを
$[x_1, x_2, \dots, x_N]
s.t. x_{i-1}<=x_i(i=1,...,N)$
$[y_1, y_2, \dots, y_N]
s.t. y_{i-1}<=y_i(i=1,...,N)$
とすれば
$min = |x_1-y_1|+|x_2-y_2|+ \cdots + |x_N-y_N|$
が成り立つ。
簡易的な証明
仮に上のような大小関係の時、$|x_1-y_1|+|x_2-y_2| < |x_2-y_1|+|x_1-y_2|$です。
他の考えうる大小関係すべてにおいて考えれば2点間においてこの$|x_1-y_1|+|x_2-y_2| < |x_2-y_1|+|x_1-y_2|$が成り立ちます。
これを拡張してnについても成り立つことを確認すれば数学的帰納法より原理が証明されます。