Как найти минимальное положительное число K для массива, чтобы сделать массив в строго возрастающем порядке

Как найти минимальное положительное число K такое, что для каждого элемента массива добавление или вычитание числа из [-K, K] может привести к строго возрастающему массиву?

Например:

  • массив [10, 2, 20]
  • min K равно 5, возможным результатом является [10-5, 2 + 4, 20]
  • k = 4 не в порядке, потому что 10-4 == 2 + 4; массив не может быть преобразован строго в порядке возрастания

Мое предположение выглядит следующим образом

определить f (i, j) = a [i] - a [j] + ji-1 (для я < j и a [i] > a [j]: все пары обратного порядка)

Мин K должен удовлетворять условию:

2 * K > max f (i, j)

потому что, если пара (i, j) не находится в порядке возрастания, a [j] может добавить только K не более, a [i] может вычесть K не более, и вам нужно оставить место для элементов между [ i] и a [j] (поскольку он строго возрастает), поэтому (a [j] + K) - (a [i] - K) должно быть больше (j-i-1) (длина между ними). ​​

Итак, k >= max f (i, j)/2 + 1

Проблема заключается в том, что я не могу доказать, является ли k = max f (i, j)/2 + 1 ОК или нет?

больше подсказок:

Я думал о том, что найти алгоритм для определения заданного К достаточно или нет, тогда мы может использовать алгоритм, чтобы попробовать каждый K от возможного минимума, чтобы найти решение.

i'v придумал такой алгоритм:

for i in n->1  # n is array length
if i == n:
    add K to a[i]   # add the max to the last item won't affect order
else:
    # the method is try to make a[i] as big as possible and still < a[i+1]
    find a num k1 in [-K, K] to make a[i] to bottom closest to a[i+1]-1
    if found:
        add k1 to a[i]
    else no k1 in [-K, K] can make a[i] < a[i+1]
        return false
return true

Я тоже такой алгоритм прав или нет

Ответы

Ответ 1

Я думаю, что твоя догадка правильная, но я тоже не могу это доказать:-) Вместо этого я начал бы с упрощения вопроса

Как найти минимальное положительное число K такое, что для каждого элемента массива добавление или вычитание числа из [-K, K] может привести к строго возрастающему массиву?

к этому эквивалентному, добавив "K:

Как найти минимальное положительное число 2 * K такое, что для каждого элемента массива добавление числа из [0, 2 * K] может привести к строго возрастающему массиву?

Мы можем легко решить это путем итерации массива и отслеживания необходимого значения 2K для выполнения условия. Он очень похож на @ruakh один, но без вычитаний:

k2 = 0
last = arr[0]
for each cur in arr from 1
    if cur + k2 <= last
        last ++
        k2 = last - cur
    else
        last = cur
k = ceil ( k2 / 2 )

Ответ 2

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

Например, в Java:

int[] array = { 10, 2, 20 };
int K = 0, last = array[0];
for (int i = 1; i < array.length; ++i) {
    if (last >= array[i] + K) {
        // If we're here, then our value for K wasn't enough: the minimum
        // possible value of the previous element after transformation is still
        // not less than the maximum possible value of the current element after
        // transformation; so, we need to increase K, allowing us to decrease
        // the former and increase the latter.
        int correction = (last - (array[i] + K)) / 2 + 1;
        K += correction;
        last -= correction;
        ++last;
    } else {
        // If we're here, then our value for K was fine, and we just need to
        // record the minimum possible value of the current value after
        // transformation. (It has to be greater than the minimum possible value
        // of the previous element, and it has to be within the K-bound.)
        if (last < array[i] - K) {
            last = array[i] - K;
        } else {
            ++last;
        }
    }
}