Ссылка: http://www.usaco.org/index.php?page=viewproblem2&cpid=989

Примечание. Эта задача имеет более простую жадную реализацию… это была «моя самая сложная проблема», потому что я выбрал другой (более эффективный) подход.

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

Если бы X не существовало, то очевидной стратегией было бы максимальное увеличение текущего добавляемого элемента → это, естественно, становится суммой натуральных чисел. Давайте определимtкак первое число такое, что (n*(n+1))/2 ≥ k, тогда верно, что любой другой способ построить сумму k потребуется не менее t шагов. Фактически, без ограничения X оптимальным ответом всегда будет t. Мы можем вычислить tза время O(log(sqrt(n)) с помощью бинарного поиска, поскольку верхняя граница дляt приблизительно равно sqrt(n*2).

Геометрическая интерпретация этого рассуждения показана на рисунке:

Здесь каждый столбец представляет собой добавляемое целое число, причем максимально возможное число равно t.

Но проблему можно лучше представить следующим образом:

Естественно, с добавленным ограничением X все квадраты внутри серого прямоугольника больше нельзя использовать. Кроме того, ступенчатая структура, построенная до t, устаревает: мы больше не можем использовать последнюю ступеньку, так как ее абсолютная разница с X больше 1.

Оптимальная структура, которую мы можем получить без добавления столбцов и которая соответствует ограничению X, — это [1..X]rows + pyr(t-x+1).

Сегмент t-x+1 показан фиолетовым цветом, а pyr(t-x+1) завернут с зеленым. В более общем смысле pyr(x) можно определить как «максимальную пирамидальную структуру с основанием x» (вид).

Вот некоторые примеры:

Причина, по которой пирамиды с основанием X имеют только столбцы X-2, заключается в том, что я рассматриваю только добавленные квадраты, которые пирамида внесет в исходную структуру. Способ построения формулы для pyr():

Используя это рассуждение, ответом является просто минимальное количество столбцов, в которых мы можем распределить «оставшиеся ячейки» = k - gauss(X) - (t-X) *X - пир(t-X+1):

Можно вычислить, сколько столбцов необходимо за время O(sqrt(k)) (даже возможно сделать это за O(log(sqrt(sqrt(k))) с помощью бинарного поиска). Способ сделать это — сохранить «пирамидоподобное» сложение и расширить структуру до точки, в которой k достигается или превышается.

Ответ: t + cols_added