Уменьшить массив, добавив элементы

Question

Я столкнулся с этим вопросом в тесте.

Учитывая массив, уменьшите массив до одного элемента с минимальными затратами. Для уменьшения удалите два элемента из массива, добавьте эти два числа и сохраните сумму обратно в массив. Стоимость каждой операции - это сумма элементов, удаленных на этом этапе.

Пример, пусть массив со A = [1,2,3]

Затем можно удалить 1 и 2, добавить оба из них и сохранить сумму обратно в массив. Стоимость этого шага будет (1 + 2) = 3.

Так А = [3,3], стоимость = 3

На втором этапе, можно удалить оба элемента из массива и сохранить сумму снова в массиве. Стоимость этой стадии будет 3 + 3 = 6.

Таким образом, А = [6], стоимость = 6

Так общая стоимость оказывается 9 (6 + 3).

Я попробовал сортировку массива и добавление элементов от уменьшения к увеличению, но это не удается, если есть повторяющиеся элементы.

Псевдо код моего алгоритма

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, согласно приведенному выше алгоритму.

Однако, если мы суммируем первые два элемента и последние два элемента, а затем суммируем оставшиеся два элемента, тогда общая стоимость оказывается равной 40. (На первом этапе стоимость = 10 * 2 и на следующем шаге другой 20)

Что может быть эффективным алгоритмом для этого?

Answer 1

Вы были на правильном пути, сортируя массив и суммируя самые нижние элементы. Проблема заключается в следующем: сумма двух нижних элементов может быть больше, чем следующий элемент после них, поэтому вы не можете просто поставить ее спереди. Но он также может быть меньше последнего элемента, поэтому вы также не можете поместить его в спину. Вы должны положить сумму в то место, где она принадлежит 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. Они доступны на большинстве языков и предоставляют методы для получения и удаления самого маленького элемента и для вставки элемента в нужное место. Вот пример в Python:

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 

И если вы не можете использовать кучи, вы можете перебирать массив, чтобы найти подходящее место, чтобы положить суммированный элемент, или использовать бинарный поиск, чтобы сделать это быстрее.

Answer 2

Ваш массив всегда будет уменьшаться до sum всех его элементов. "cost "такого снижения может варьироваться, хотя. минимальная "cost" может быть достигнуто путем добавления двух минимальных элементов, которые существуют в настоящее время в массиве.

Мин кучи может быть использован очень эффективно решить эту проблему. Ниже приведен пример, в 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, но несколько улучшает наше время выполнения.