Правильность жадного алгоритма

Ответ 1

• Корректность:

  • Предположим, что максимальное число пар, которое может быть удалено, k. Утверждение: существует оптимальное решение, в котором первые элементы всех пар являются k наименьшими элементами массива. Доказательство. Я покажу, что можно преобразовать любое решение в одно, содержащее первые элементы k в качестве первых элементов всех пар.

    • Предположим, что мы имеем две пары (a, b), (c, d) такие, что a <= b <= c <= d, 2 * a <= b и 2 * c <= d. В этом случае допустимы пары (a, c) и (b, d). И теперь мы имеем a <= c <= b <= d. Таким образом, мы всегда можем преобразовать пары таким образом, чтобы первый элемент из любой пары не был больше второго элемента любой пары.

    • Когда у нас есть это свойство, мы можем просто подставить наименьший элемент среди всех первых всех элементов всех пар с наименьшим элементом в массиве, второй наименьший среди всех первых элементов - со вторым наименьшим элементом в массива и т.д., не лишая при этом никакой пары.

  • Теперь мы знаем, что существует оптимальное решение, содержащее k наименьшие элементы. Понятно, что мы не можем сделать ответ хуже, взяв наименьший неиспользуемый элемент (делая его больше, может только уменьшить ответ для следующих элементов), который подходит каждому из них. Таким образом, это решение является правильным.

  • Заметка о случае, когда длина массива нечетна: неважно, где находится средний элемент: к первой или ко второй половине. В первом тайме это бесполезно (во втором тайме не хватает элементов). Если мы перейдем ко второй половине, это бесполезно два (допустим, что мы это взяли. Это означает, что во втором тайме есть "свободное пространство". Таким образом, мы можем сдвинуть некоторые элементы на единицу и избавиться от него).

• Оптимальность с точки зрения временной сложности: временная сложность этого решения O(n). Мы не можем найти ответ, не читая весь ввод в худшем случае, а чтение уже O(n) времени. Таким образом, этот алгоритм оптимален.

Ответ 2

Предпочитая свой метод. Индексы основаны на 0.

Обозначим в общем случае:

• end_1 = floor(N/2) граница (включительно) первой части.

Обозначим при повторении:

• i индекс в первой части, j индекс во второй части,
• оптимальное решение до этой точки sol(i,j) (с использованием алгоритма спереди),
• которые по-прежнему оптимально поддерживаются в паре за точкой (i,j), т.е. из (i+1,j+1) onward rem(i,j) (может быть рассчитан с использованием алгоритма со спины),
• окончательное оптимальное решение может быть выражено как функция любой точки как sol(i,j) + rem(i,j).

Наблюдение №1: при выполнении алгоритма с фронта все точки в диапазоне [0, i] используются, некоторые точки из диапазона [end_1+1, j] не используются (мы пропускаем a(j) не очень сильно). При выполнении алгоритма с обратной стороны некоторые точки [i+1, end_1] не используются, и используются все теги [j+1, N] (мы пропускаем a(i) не достаточно мало).

Наблюдение № 2: rem(i,j) >= rem(i,j+1), потому что rem(i,j) = rem(i,j+1) + M, где M может быть 0 или 1 в зависимости от того, можем ли мы соединиться с a(j) с некоторым неиспользуемым элементом из диапазона [i+1, end_1].

Аргумент (от противного): допустим 2*a(i) <= a(j) и что не спаривание a(i) и a(j) дает как минимум хорошее окончательное решение. По алгоритму мы попытались бы затем скомпоновать a(i) и a(j+1). Так как:

• rem(i,j) >= rem(i,j+1) (см. выше),
• sol(i,j+1) = sol(i,j) (так как мы не спарили a(i) и a(j))

получаем, что sol(i,j) + rem(i,j) >= sol(i,j+1) + rem(i,j+1), что противоречит предположению.