隣り合った差の合計が2未満になるような数の順列を与えるアルゴリズム

Question

これは宿題の問題でしたが、講師が解決策を説明したところで私はまだそれを理解できませんでした...

区間[0,1]（つまりx1、x2、x3、...、xn）にn個の実数が与えられた場合、最悪の場合に線形時間で実行され、これらのn個の数字のうち、隣接する数字の差の合計が2未満であるようにします。ヒントは「バケツ」です。

Answer 1

です。このようにすることができます。 [0, 1]をkセグメントに：[0, 1/k),[1/k, 2/k)、... [(k-1)/k, 1]に分割します。

これで、最初のセグメントに収まるすべての数字をリストに入れ、新しいリストに入れます。これは、1回のパスで実行できるので、O(n)です。

ここで必要な合計額を検討してください。同じセグメント内の数字の差分は、最大で1/kであり、そのような差の数はn-(k-1)です。残りの(n-1)の差分は、隣接するバケットからの数値の間にあります。それは全体として（明らかですが、なぜですか？）1以下です。合計額は(n-k+1)/k + (k-1)/kです。 kのサイズが十分に小さい場合は、十分に小さくすることができます。

---

詳細：

のは、2色に私たちの違いをペイントしてみましょう：同じセグメントの数字の違いは青い塗られており、異なるセグメントの数字との違いは、赤の塗装されています。注文のおかげで、最初のセグメント（0の可能性あり）の番号だけが2番目のセグメントの番号などとなります。だから、赤の違いよりも最初にいくつかの青の違いがあります。もう一つの赤の違いなどです。

赤の違いの数は何ですか？明らかに、k-1赤の違いよりも、右ですか？各赤の差はあるセグメントから高いセグメントにジャンプするためです。残りの違いは青です。

ここで、青の差は1/k以下です。これは、被減数と減数が同じセグメントに由来するためです。そして、完全にすべての赤の違い（つまり、それらの和である！）（これは宿題の問題であるとして、今の残りの部分をスキップします。）1を超えない

---

訂正：
すべての赤の合計差は2-2/kを超えない。何故ですか？さて、見てみましょう。第1の赤の差は、最悪の場合には、あるセグメントAの始めから他のセグメントの末尾Bの終わりまでである可能性がある。第2のものは、Bの最初のから、最悪の場合、他のセグメントの末尾Cまでです。したがって、差の合計で、最初と最後を除くすべてのセグメントが最大で2回カウントされます。

Answer 2

間隔を等間隔に分割してください。今度は、それらが所属する間隔に数字を任意の順序で入れて、これがあなたの問題を解決することを証明してください。

Answer 3

バケットソートについて知りましたか？ http://en.wikipedia.org/wiki/Bucket_sort

もソートされた配列の挙動を見て： {0、0.5、0.75、1}：{ ：差の和が1

ソートされていないアレイの動作にそれを比較され.75、.5、0,1}：差の合計は1.75