Преобразование массива в отсортированный с использованием только двух операций

Ответ 1

ПРИМЕЧАНИЕ. Первоначальный ответ был заменен на тот, в котором у меня гораздо больше уверенности (и я тоже могу это объяснить). Оба ответа дали одинаковые результаты в моем наборе тестовых случаев.

Вы можете решить эту проблему с помощью подхода динамического программирования. Главное наблюдение заключается в том, что никогда не имеет смысла уменьшать число до значения, не найденного в исходном массиве. (Неофициальное доказательство: предположим, что вы уменьшили число O1 до значения X, которое не находится в исходной последовательности, чтобы избежать удаления числа O2 > X из последовательности результатов. Затем вы можете уменьшить O1 до O2 и уменьшите стоимость на O2-X).

Теперь решение становится понятным: это DP в двух измерениях. Если мы сортируем элементы отдельных элементов исходной последовательности d в отсортированный массив s, длина d становится первым измерением DP; длина s становится второй размерностью.

Объявляем dp[d.Length,s.Length]. Значение dp[i,j] - это стоимость решения подзадачи d[0 to i], сохраняя последний элемент решения при s[j]. Примечание: эта стоимость включает стоимость устранения d[i], если она меньше s[j].

Первая строка dp[0,j] вычисляется как стоимость обрезки d[0] до s[j], или ноль, если d[0] < s[j]. Значение dp[i,j] следующей строки вычисляется как минимум dp[i-1, 0 to j] + trim, где trim - это стоимость обрезки d[i] до s[j] или d[i], если ее нужно устранить, поскольку s[j] больше d[i].

Ответ вычисляется как минимум последней строки dp[d.Length-1, 0 to s.Length].

Вот реализация в С#:

static int Cost(int[] d) {
    var s = d.Distinct().OrderBy(v => v).ToArray();
    var dp = new int[d.Length,s.Length];
    for (var j = 0 ; j != s.Length ; j++) {
        dp[0, j] = Math.Max(d[0] - s[j], 0);
    }
    for (var i = 1; i != d.Length; i++) {
        for (var j = 0 ; j != s.Length ; j++) {
            dp[i, j] = int.MaxValue;
            var trim = d[i] - s[j];
            if (trim < 0) {
                trim = d[i];
            }
            dp[i, j] = int.MaxValue;
            for (var k = j ; k >= 0 ; k--) {
                dp[i, j] = Math.Min(dp[i, j], dp[i - 1, k] + trim);
            }
        }
    }
    var best = int.MaxValue;
    for (var j = 0 ; j != s.Length ; j++) {
        best = Math.Min(best, dp[d.Length - 1, j]);
    }
    return best;
}

Эта прямая реализация имеет пространственную сложность O(N^2). Вы можете уменьшить его до O(N), заметив, что одновременно используются только две последние строки.

Ответ 2

Я предполагаю, что "сортировка" означает наименьшие значения в начале массива, учитывая характер разрешенных операций.

Граница производительности между двумя операциями возникает, когда стоимость удаления элемента из последовательности равна стоимости либо уменьшения всех более значимых элементов до и включая правонарушителя, либо удаления всех менее значимых элементов после преступник. Вы выбираете между декрементами предыдущих элементов или удалением более поздних элементов на основании того, почему элемент-нарушитель не соответствует последовательности. Если это меньше, чем предыдущий элемент, рассмотрите декремент предыдущих элементов; если он больше, чем следующий элемент, рассмотрим удаление более поздних элементов.

Некоторые примеры:

10 1 2 3 4 5

Уменьшение 10 к 1, стоимость 9.

1 2 3 4 10 4

Удалить 4, стоимость 4.

1 2 3 4 10 5

Удалите 5 или уменьшите 10 до 5, стоимость 5.

5 6 7 8 1 10

Удалить 1, стоимость 1.

5 6 7 8 6 10

Сокращение 7 и 8 до 6, стоимость 3.

2 1 1 4 2 4 4 3

Уменьшить первый 1, первый 4 на два и два других четыре раза один раз, стоимость 5.

Простейшая реализация для поиска решений основана на установлении знаний, поэтому она очень неэффективна. К счастью, на этот вопрос все равно. Идея состоит в том, чтобы пройти массив и принять решение о том, следует ли удалять или уменьшать, чтобы исправить набор, когда встречается элемент вне последовательности. Более эффективная реализация этого будет заключаться в использовании текущих итогов (в отличие от методов расчета) и перемещения массива дважды, вперед и назад. Я написал макет более простой версии, так как мне кажется, что ее легче читать.

Pseudocode, возвращает общую стоимость:

if array.Length < 2 : return 0; // no sorting necessary

resultArray = array.Copy();
int cost = 0;

for i = 0 to array.Length - 1 :

if i > 0 and array[i-1] > array[i] :

if CostToDecrementPreviousItems(i, array[i]) > array[i]) :
resultArray[i] = -1;
cost += array[i];
else :
cost += DecrementItemsThroughIndexGreaterThanValue(resultArray, i, array[i]);
end if

else if i < array.Length - 1 and array[i+1] < array[i] :

if CostToRemoveLaterItems(i, array[i]) > array[i] :
resultArray[i] = -1;
cost += array[i];
else :
cost += RemoveItemsAfterIndexGreaterThanValue(resultArray, i, array[i]);
end if

end if
end for

RemoveNegativeElements(resultArray);
array = resultArray;

return cost;

Надеемся, что вызовы метода undefined являются пояснительными.

Ответ 3

• Построить граф решений, добавить к нему стартовую вершину. Каждая вершина содержит "уровень обрезки", то есть значение, на которое должно быть уменьшено все значения массива слева от текущего node. Начало вершины "уровень обрезки" - бесконечность. Каждый край графика имеет значение, соответствующее стоимости решения.
• Для каждого элемента массива, начиная с самого правого, делайте шаги 3.. 5.
• Для каждой листовой вершины выполните шаги 4.. 5.
• Создайте до 2 исходящих ребер, (1) со стоимостью удаления элемента массива и (2) со стоимостью обрезки всех элементов влево (в точности, стоимость уменьшения "уровня отделки" ).
• Подключите эти ребра к вновь созданным вершинам, одну вершину для каждого элемента массива и каждый уровень обрезки.
• Найдите кратчайший путь от начальной вершины до одной из вершин, соответствующей самому крайнему элементу массива. Длина этого пути равна стоимости решения.
• Уменьшить и удалить элементы массива в соответствии с графиком принятия решений.

Этот алгоритм можно рассматривать как оптимизацию подхода грубой силы. Для поиска грубой силы, начиная с самого правого элемента массива, создайте двоичное дерево решений. Каждая вершина имеет 2 исходящих ребра, один для решения "удалить" , другое решение "trim". Стоимость решения связана с каждым ребром. "Уровень обрезки" связан с каждой вершиной. Оптимальное решение определяется кратчайшим путем в этом дереве.

Удалите все пути, что, очевидно, неоптимально. Например, если наибольший элемент является последним в массиве, решение "обрезать" имеет нулевое значение, а решение "удалить" является неоптимальным. Удалите путь, начиная с этого решения "удалить" . После этой оптимизации дерево решений более разреженное: некоторые вершины имеют 2 исходящих ребра, некоторые - только один.

На каждом уровне глубины дерево решений может иметь несколько вершин с одинаковым уровнем обрезки. Подэлементы, начиная с этих вершин, идентичны друг другу. Это хорошая причина для присоединения всех этих вершин к одной вершине. Это преобразует дерево в граф, содержащий не более n ²/2 вершин.

Сложность

Простейшей реализацией этого алгоритма является O (n ³), потому что для каждой из O (n ²) вершин он вычисляет затраты на обрезку итеративно, в O (n).

Повторные расчеты затрат на обрезку не нужны, если имеется достаточно памяти для хранения всех результатов частичной подгонки. Для этого может потребоваться O (n ²) или даже O (n) пространство.

При такой оптимизации этот алгоритм O (n ²). Из-за простой структуры графика поиск кратчайшего пути имеет сложность O (n ²), а не O (n ² * log (n)).

Реализация С++ 11 (как пространственная, так и временная сложность O (n ²)):

//g++ -std=c++0x
#include <iostream>
#include <vector>
#include <algorithm>

typedef unsigned val_t;
typedef unsigned long long acc_t; // to avoid overflows
typedef unsigned ind_t;
typedef std::vector<val_t> arr_t;

struct Node
{
  acc_t trimCost;
  acc_t cost;
  ind_t link;
  bool used;

  Node()
  : trimCost(0)
  , used(false)
  {}
};

class Matrix
{
  std::vector<Node> m;
  ind_t columns;

  public:
  Matrix(ind_t rows, ind_t cols)
  : m(rows * cols)
  , columns(cols)
  {}

  Node& operator () (ind_t row, ind_t column)
  {
    return m[columns * row + column];
  }
};

void fillTrimCosts(const arr_t& array, const arr_t& levels, Matrix& matrix)
{
  for (ind_t row = 0; row != array.size(); ++row)
  {
    for (ind_t column = 0; column != levels.size(); ++column)
    {
      Node& node = matrix(row + 1, column);
      node.trimCost = matrix(row, column).trimCost;

      if (array[row] > levels[column])
      {
        node.trimCost += array[row] - levels[column];
      }
    }
  }
}

void updateNode(Node& node, acc_t cost, ind_t column)
{
  if (!node.used || node.cost > cost)
  {
    node.cost = cost;
    node.link = column;
  }
}

acc_t transform(arr_t& array)
{
  const ind_t size = array.size();

  // Sorted array of trim levels
  arr_t levels = array;
  std::sort(levels.begin(), levels.end());
  levels.erase(
    std::unique(levels.begin(), levels.end()),
    levels.end());

  // Initialize matrix
  Matrix matrix(size + 1, levels.size());
  fillTrimCosts(array, levels, matrix);
  Node& startNode = matrix(size, levels.size() - 1);
  startNode.used = true;
  startNode.cost = 0;

  // For each array element, starting from the last one
  for (ind_t row = size; row != 0; --row)
  {
    // Determine trim level for this array element
    auto iter = std::lower_bound(levels.begin(), levels.end(), array[row - 1]);
    const ind_t newLevel = iter - levels.begin();

    // For each trim level
    for (ind_t column = 0; column != levels.size(); ++column)
    {
      const Node& node = matrix(row, column);
      if (!node.used)
        continue;

      // Determine cost of trimming to current array element level
      const acc_t oldCost = node.trimCost;
      const acc_t newCost = matrix(row, newLevel).trimCost;
      const acc_t trimCost = (newCost > oldCost)? newCost - oldCost: 0;

      // Nodes for "trim" and "delete" decisions
      Node& trimNode = matrix(row - 1, newLevel);
      Node& nextNode = matrix(row - 1, column);

      if (trimCost)
      {
        // Decision needed, update both nodes
        updateNode(trimNode, trimCost + node.cost, column);
        updateNode(nextNode, array[row - 1] + node.cost, column);
        trimNode.used = true;
      }
      else
      {
        // No decision needed, pass current state to the next row node
        updateNode(nextNode, node.cost, column);
      }

      nextNode.used = true;
    }
  }

  // Find optimal cost and starting trim level for it
  acc_t bestCost = size * levels.size();
  ind_t bestLevel = levels.size();
  for (ind_t column = 0; column != levels.size(); ++column)
  {
    const Node& node = matrix(0, column);
    if (node.used && node.cost < bestCost)
    {
      bestCost = node.cost;
      bestLevel = column;
    }
  }

  // Trace the path of minimum cost
  for (ind_t row = 0; row != size; ++row)
  {
    const Node& node = matrix(row, bestLevel);
    const ind_t next = node.link;

    if (next == bestLevel && node.cost != matrix(row + 1, next).cost)
    {
      array[row] = 0;
    }
    else if (array[row] > levels[bestLevel])
    {
      array[row] = levels[bestLevel];
    }

    bestLevel = next;
  }

  return bestCost;
}

void printArray(const arr_t& array)
{
  for (val_t val: array)
    if (val)
      std::cout << val << ' ';
    else
      std::cout << "* ";
  std::cout << std::endl;
}

int main()
{
  arr_t array({9,8,7,6,5,4,3,2,1});
  printArray(array);

  acc_t cost = transform(array);
  printArray(array);
  std::cout << "Cost=" << cost << std::endl;

  return 0;
}