入力は、実数 x1、x2、...、x2n のシーケンスです。これらの数値をペアにして n ペアにしたいと思います。i 番目のペア (i = 1, 2, ..., n) について、そのペアの数の合計を Si とします。(たとえば、i 番目のペアとして x(2i−1) と x2i をペアにする場合、Si = x(2i−1) + x2i)。Maxi[Si] が最小になるように、これらの数値をペアにします。この問題を解決する貪欲なアルゴリズムを設計します。
それが問題です; 私の解決策は、単純に数字を並べ替えて、最初と最後の要素をペアにし、1 を加算/1 を減算して繰り返すことです。アルゴリズムは各ペアを最適化しようとするため、貪欲になります。これを行う線形時間アルゴリズムがあるかどうか疑問に思っていますか?
PS: これは宿題ではありませんが、非常によく似ていることは理解しています。
貪欲で概算にしたい場合は、データに対して固定サイズのウィンドウを1回実行し、ウィンドウ内の数字のみをペアにすることができます-ウィンドウの左端にあるものとウィンドウ内の他の数字-1つにマークを付けます左端ではないので、再利用しません。ウィンドウを進めます。左端のものは再利用されません。これは、局所的にのみ最適であるという意味で貪欲です。リストが一様にランダムであることがわかっている場合、リストは近い可能性があり、線形である可能性があります。これは、一定の長さ k のリストのソートは、N に対して一定の時間であるためです。リストの分布に関する他の知識があれば、次のバリアントを使用できます。まだ O(N) であり、概算のみです。
いいえ。これを行うための線形時間アルゴはありません。入力番号は任意の順序である可能性があるため、min Maxi[Si] ですぐにペアリングを行うことはできません。現在のソリューションはシンプルで優れています。
実行時間を改善するための提案:
入力数値から二分木を作成できます (これには O(nlog(n)) 時間がかかります)。ツリーを順番にトラバーサルし、(first+i, last-i) 要素 (0 から n/2 までの i) からペアを作成します。