1632
правки
Изменения
м
Несложно заметитьТак как мы выбираем два элемента с наименьшими частотами <tex>f_1</tex> и <tex>f_2</tex>, то в силу выбора элементов их суммарная частота <tex>S = f_1 + f_2</tex> будет не больше суммы двух любых других из нерассмотренных частот, следовательно, никакая из последующих сумм не окажется меньше <tex>S</tex>. Докажем, что в этом массиве элементы тоже будут идти по неубыванию<tex>S</tex> не меньше значений, добавленных во второй массив на предыдущих итерациях. Допустим, что это не так и на каком-то шаге сумма получилась меньше чем предыдущаямы добавили в массив число <tex>S_1</tex> такое, что <tex>S_1 > S</tex>. Это значит, что на одной из итераций мы выбрали два элемента таким образом, что хотя бы один из них был больше <tex>f_1</tex> либо больше <tex>f_2</tex>. Но так как первый массив отсортирован по возрастанию, а второй изначально заполнен <tex>\infty</tex>, но это противоречит тому, что на каждом шаге каждой итерации мы выбираем два минимальных (тзначения.е. на каждом последующем шаге мы выбираем два минимума Следовательно, наше предположение неверно, сумма <tex>S</tex> является наибольшей из элементов не меньших, чем на предыдущем шаге)рассмотренных ранее сумм и второй массив отсортирован по возрастанию.
rollbackEdits.php mass rollback
# Два первых элемента второго массива.
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы. Докажем, что второй массив остается отсортированным по возрастанию после каждой итерации.
На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, поэтому асимптотика программы составляет <tex>O(n)</tex>.
b[k] = <tex>\infty</tex>
'''for''' k = 0 '''to''' n - 1
'''if''' a[i] + a[i + 1] <= a[i] + b[j] '''and''' a[i] + a[i + 1] <= b[j] + b[j + 1]//уже на 3-ей итерации выход за границу массива //i = 4, i + 1 = 5, a[5] = undefined
b[k] = a[i] + a[i + 1]
ans += b[k]
