Перераспределение камней

Сделаем два наблюдения:

1) Первым делом переформулируем, что требуется в задаче. Фактически, в задаче требуется найти отрезок-ответ из n сундуков, на котором лежит максимальное количество камней (тогда как раз останется только переложить камни из сундуков, не попадающих в отрезок, и максимизировав количество камней на отрезке мы минимизируем число перекладываний).

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

Теперь, после этих двух наблюдений задача решается очень просто: отсортируем массив с номерами сундуков, где лежат камни, затем переберем камень ai, который будет лежать в самом левом сундуке отрезка-ответа, а дальше двоичным поиском найдем количество камней, лежащих на отрезке [ai, ai + n - 1]. Из всех вариантов возьмем отрезок с максимальным количеством камней c на нем. Ответом будет являться n - c. Итоговая асимптотика: .

Также можно вторую часть решения делать за O(n) с помощью двух указателей, однако асимптотика все равно останется из-за сортировки.