要素を追加して配列を減らす

Question

私はテストでこの質問に出くわしました。

配列を指定すると、最小コストで単一の要素に配列を縮小します。削減するには、配列から2つの要素を削除し、その2つの数を加算し、合計を配列内に戻します。各操作のコストは、そのステップで削除された要素の合計です。

例、その後、我々は彼らの両方を追加し、1と2を削除することができますし、配列に戻って合計を保つ配列にA = [1,2,3]

をしましょう。このステップのコストは、（1 + 2）であろう。3.

したがってA = [3,3]、第2のステップでコスト= 3

=、我々は、アレイからの両方の要素を削除して和を保つことができます再び配列に戻ります。このステップのコストは= 6

コストがそう総コストは9（6 + 3）であることが判明し、A = [6]、SO 3 + 3 = 6

あろう。

私は配列をソートしようとしていますが、要素を増やしていくほど減らしていますが、重複要素があると失敗します。

私のアルゴリズムの擬似コード

sort(Array) 
cost = 0 
for(i=0; i<Array.length - 1; i++) { 
    Array[i+1] = Array[i] + Array[i+1] 
    cost = cost + Array[i+1] 
} 

上記のアルゴリズムが働いていませんでした。私はそれが失敗する可能性のあるケースを考え出した。 Array = [5,5,5,5]の場合、上記のアルゴリズムに従ってCost = 45になります。

ただし、最初の2つの要素と最後の2つの要素を合計し、残りの2つの要素を合計すると、合計コストは40になります（最初の手順ではコスト= 10 * 2、次の手順別の20）

これに対して効率的なアルゴリズムは何でしょうか？

Answer 1

あなたは、配列をソートし、最も低い要素を最初に合計して正しい軌道に乗っていました。問題は次のとおりです。2つの最も低い要素の合計がそれらの次の要素よりも大きくなる可能性があります。したがって、それを正面に置くことはできません。しかし、最後の要素よりも小さくなる可能性もあるので、後ろに置くこともできません。あなたはそれをw.r.tに所属する場所に入れるだけです。ソート。

例：あなたのリストが[1, 1, 3, 3]であれば、1+1は[2, 3, 3]すなわち、前に配置する必要がありますが、私たちは[2, 2, 3, 3]を持っている場合は、合計2+2はバック[3, 3, 4]に入れなければならず、[2, 2, 3, 5]のためである必要がありますされます中間の位置、すなわち[3, 4, 5]に入れます。

これを行う簡単な方法は、heap構造を使用することです。それらはほとんどの言語で利用でき、最小の要素を取得したり削除したり、適切な場所に要素を挿入するためのメソッドを提供します。

import heapq 
def reduce_sum(lst): 
    heapq.heapify(lst) 
    s = 0 
    while len(lst) > 1: 
     first = heapq.heappop(lst) 
     second = heapq.heappop(lst) 
     s += first + second 
     heapq.heappush(lst, first + second) 
    return s 

reduce_sum([1,2,3])  # 9 
reduce_sum([5, 5, 5, 5]) # 40 

をそして、あなたはヒープを使用できない場合、あなたはまだ加算された要素を入れて、またはこれより速く行うためにバイナリ検索を使用するために適切な場所を見つけるために、配列を反復処理することができます。ここでは、Pythonでの例です。

Answer 2

配列は常にすべての要素のsumに縮小されます。この減少の"cost "はいえ変化してもよい。 最小​​現在アレイに存在する2つの極小の要素を追加することによって達成することができる。

最小ヒープは非常に効率的にこの問題を解決するために使用することができる。ここでは、Javaの例です。

public int[] sumAndCost(Integer[] arr) { 
     PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Arrays.asList(arr)); 
     int sum = priorityQueue.poll(); 
     int cost = 0; 
     while (!priorityQueue.isEmpty()) { 
      int currentElement = priorityQueue.poll(); 
      if (currentElement < sum) { 
       priorityQueue.add(sum); 
       sum = currentElement; 
      } else { 
       sum += currentElement; 
       cost += sum; 
       continue; 
      } 

      sum += priorityQueue.poll(); 
      cost += sum; 
     } 

     return new int[] {sum, cost}; 
    } 

これは、合計して、任意の配列のためのコストの両方を返します。

条件文は少しuncessary見てもよいが、それは多少私たちのランタイムを向上させます。