丸でキャンディーに配布する最小化手順

Question

円にはnの子供がいます。それぞれにはいくつかのキャンディーがあります（マイナス、プラス、ゼロ）。彼らは一度に彼らの隣人に一つのキャンディーを与えることができます。最終的な結果は、すべてが最小限のステップでキャンディーをゼロにする必要があるということです。

我々は(-4, -2, 4, 2)キャンディーと4人の子供を持っていると仮定し、次いで配列は

1. （-3、-2、4、1）
2. （-2、-2、4、0）
あろう
3. （-2、-1、3、0）
4. （-2、0、2、0）
5. （-2、1、1、0）
6. （-2、2、0、0 ）
7. （-1,1,0、 0）
8. （0、0、0、0）

これは一つの可能​​な答えは、私はステップの最小数を見つける必要があります。

• ループ1：隣人が正のキャンディーを持っているならば、キャンディーの数がゼロに等しくなるまで、負のキャンディーで隣人にそれを与えるとの和に与えられたキャンディーの数を追加し、見つけます。

• ループ2：隣人の隣人が肯定的なキャンディーを持っているかどうかを調べ、キャンディーの数がゼロになるまでネガティブキャンディーでそれを与え、2（合計に与えられるキャンディーの数）を加えます。

• など。

私の解決策の複雑さはTLEを引き起こしています。複雑さを減らすために私は何ができますか？

Answer 1

詳細をループする必要はありません。それぞれの場所にあるキャンディの数をX1、X2、X3、X4と書く。 X1が左からk個のキャンディーを受け取ったとします（つまり、X4の場合）。その後、X1 + kキャンディーがあるので、これをその右に渡す必要があります。それから、X2はX1 + X2 + kのキャンディを持っているので、右にこれを渡す必要があります。 X3はX1 + X2 + X3 + kキャンディーを持つので、X4にこれを渡す必要があります。私たちはX4がk個のキャンディーを通過したことを知っており、これはチェックします（X1 + X2 + X3 + X4 = 0で、それがなければ解はありません）。

これは| k | + | X1 + k | + | X1 + X2 + k | + | X1 + X2 + X3 + k |私たちがkを推測すれば、私たちはいくつのステップを取るべきかを知っています。 kの最高の価値は何ですか？ kを増加させると、+ ve項X1 + X2 + ... kがさらにあれば総和が増加し、-ve項が増えると減少する。したがって、kの最良の値は、| k |、| X1 + k |の半分がちょうどveであり、ちょうど半分のものです。これが当てはまらない場合、kを増減することができますより良いもの - 選択するkの値は0、X1、X1 + X2、X1 + X2 + X3の中央値です。

私はあなたの例のn = 4の場合についてこれを述べましたが、これから一般的なnの答えを試すことができれば幸いです。

Answer 2

ここで適用されるメタアプローチは、ポーリングしてイベントベースにするアルゴリズムを採用することです。私はどういう意味ですか？

贈与者（菓子が> 0の子供）と募集人（飴の子供）を含む循環リンクリストを維持します。贈与者と入札者との間の距離をキーとする各隣接者（円ではなくリスト内）の贈答者ペアのエントリを含む優先度キューも維持する。

ここで、距離を1ずつ増やすのではなく、プライオリティキューを使用して、次に発生する興味深いものを把握してください。贈与者のペアが解決されるたびに、一方または両方の子供がリストから脱落するため、O（1）の簿記とキューの挿入が必要になります。

Answer 3

mcdowellaのアイデアを取って、私の言葉にそれを置くことは、（それはそれを理解するために私にしばらく時間がかかったので、このトピックに関するいくつかのhandwringingためhereを参照）、以下のように見えます。キー洞察力があります：あなたが負のお菓子を所有することができます

• 同じように、あなたは基本的に反対方向に（正）お菓子を渡して一方向に負のお菓子を渡す負のお菓子だけでなく
• を渡すことができ
• 何であれ子供が持つキャンデーの響き、誰もがゼロになるだろう。

これは次のように実装されています。開始する任意の子を選んでください（次の図の子A、4ではなく5人の子供がいる）、任意の方向を選択します（この例では反時計回り） 、そして通過を開始する。すべての子供はゼロになるためにすべてのキャンディー（正または負）を取り除かなければなりません。だから子供Aは-2キャンディーを持っているので、それを子Bに渡します。その子Bに-5キャンディーがあるので、それを子Cに渡します。今度は子供Cが-4キャンディーを持ってDに渡します。これは2番目の図であり、すべてのキャンディーは13回の移動でゼロになります。

SENTER図は最適ではありません。中心線図を通過したすべてのキャンディーは負（E-> Aパスを除く）であり、はで最初のパスから加算または減算することができます。A-> Bパスが-2ではなく+5だった場合、すべてのパスは7だけインクリメントされ、E-> Aパスは0ではなく7となり、最後にはまだキャンディーがありません。そこで、すべてのパスの絶対値の合計が最小になるように、すべてのパスを調整できる数値を求めます。最後の図では、すべてのパスに+2を追加すると、すべてのパスの絶対値の合計が7であることがわかります。例として、+3を追加すると、合計が大きくなります。したがって、すべてのパスの絶対値の合計を最小にするすべてのパスに定数を追加しようとします。

P.S.誰かがのmcdowellaの私の再通知がここにあるべきではないと思うなら、私は削除して喜んでします。