私は解決策を得たと思います。少なくとも 2 つのサンプル セットでは機能します。必ずしも答えと同じセットを返すとは限りませんが、返されるセットの最小値は同じです。それは反復的で貪欲でもあり、それは素晴らしいことであり、最適化する方法はたくさんあります。MLog(N)のようです。
重要なことは、数値は重要ではなく、それらの違いだけが重要であることを理解することです。「数字を削除」すると、実際には隣接する 2 つの違いを組み合わせているだけです。私のアルゴリズムはその違いに焦点を当てます。これらの違いの原因となった項目に戻って、削除するのは簡単なことです。
アルゴリズム
- 各数値の違いの順序付きリスト/配列を作成します。
- 最小差xを見つけます。xのカウント> 残りの M の場合、停止します。あなたはすでに最高の状態にいます。
- 左端から始まるxの各値について、その差を隣接する値の小さい方と組み合わせます (そしてそのxを削除します)。隣人の値が等しい場合、決定は任意です。xの値を持つ近傍が 1 つだけの場合は、他の近傍と結合します。([1, 1, ...] のように選択肢がない場合は、対応するXと組み合わせますが、可能であれば避けてください。)
- Mがなくなるまでステップ 2 に戻ります。
アルゴリズムに関する注意事項
ステップ 3 には、任意の決定とラベル付けした点があります。おそらくそうあるべきではありませんが、どれだけ複雑にするかが問題になるほどエッジの効いたケースに陥っています。この恣意性が、複数の異なる正解が存在することを可能にします。同じ値を持つ隣人が 2 つある場合は、この時点で任意に 1 つを選択します。理想的には、おそらく 2 離れている隣人のペアをチェックし、次に 3 など、低い方を優先する必要があります。展開中にエッジに当たってしまったらどうしよう。最終的に、この部分を完全に実行するには、この関数を再帰的に呼び出して、どちらがより適切に評価されるかを確認する必要がある場合があります。
サンプル データのウォークスルー
2番目の最初:
0 3 7 10 15 26 38 44 53 61 76 80 88 93 100 から最大 8 個を削除します。
[3, 4, 3, 5, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 8
3 を削除します。エッジの削除は、一方向にのみ追加できます。
[7, 3, 5, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 7
[7, 8, 11, 12, 6, 9, 8, 15, 4, 8, 5, 7] M = 6
次に、4 を削除します: [7, 8, 11, 12, 6, 9, 8, 15, 12, 5, 7] M = 5
次に、5 を削除します: [7, 8, 11, 12, 6, 9, 8, 15, 12, 12] M = 4
次に、6 を削除します: [7, 8, 11, 12, 15, 8, 15, 12, 12] M = 3
次に、7 を削除します: [15, 11, 12, 15, 8, 15, 12, 12] M = 2
次に、8 を削除します: [15, 11, 12, 15, 23, 12, 12] M = 1 // 注、追加の方向は任意に決定
最後に、11 を削除します: [15, 23, 15, 23, 12, 12]
答えでは、最小の差は 12 であることに注意してください。
最初の 1 つ最後
0 3 7 10 15 18 26 31 38 44 53 60 61 73 76 80 81 88 93 100 から最大 7 個を削除します。
[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 7, 1, 12, 3, 4, 1, 7, 5, 7] M = 7
1 を削除します。
[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 4, 1, 7, 5, 7] M = 6
[3, 4, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 5
4 つの 3 が残っているので、それらを削除できます。
[7, 3, 5, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 4
[7, 8, 3, 8, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 3
[7, 8, 11, 5, 7, 6, 9, 8, 12, 3, 5, 7, 5, 7] M = 2 // 右への任意の追加に注意
[7, 8, 11, 5, 7, 6, 9, 8, 12, 8, 5, 7, 5, 7] M = 1
次は 5 を削除しますが、削除できるのは 1 だけであり、3 があるため、ここで終了します。最小差は 5 で、解と一致しています。
注: SauceMasterによって提示された1、29、30、31、59のケースについて、同じX値を組み合わせることを回避するという考えから編集されました。