Минимальные затраты на установку пружин одинаковой длины
Я работаю над следующей задачей:
Вам дана отсортированная коллекция пружин. Каждый из них изготовлен в определенных размерах, и каждое растяжение или сжатие требует немалого усилия. Чтобы удлинить или укоротить пружину, которая еще не сдвинулась ни на сантиметр, требуется 1 единица усилия. Каждое последующее растяжение или сжатие одной и той же пружины требует дополнительной 1 единицы усилия. Точнее, если вы хотите удлинить пружину на D сантиметров, она приложится на 1,2,…,D последовательные единицы усилия.
Ваша задача — ответить на q вопросов о том, сколько минимальных усилий потребуется, чтобы установить одинаковую длину k-кратчайших пружин.
Ограничения: N,Q <= 106, xi <= 109
Вход:
Н, В
х1, х2, х3, ...
д1, д2, д3, ...
N - количество пружин
xi - длина i-й пружины (Обратите внимание, что xi <= xi+1)
qi - сколько пружин нужно поставить одинаковой длины в i-м вопросе
Выход: Ответы на вопросы - минимальных усилий потребуется, чтобы установить к-кратчайшие пружины одинаковой длины. Потому что ответ может быть крупным шрифтом по модулю 10^9+7.
Моя попытка решения: Я обнаружил, что минимальное усилие будет достигнуто, если пружины будут установлены на среднюю длину пружин. Однако в этом подходе сложность алгоритма составляет O(n*q), что слишком медленно для данных ограничений.
Как я могу решить эту проблему быстрее?
В своем жестком подходе я рассчитываю среднюю длину пружин, а затем линейно рассчитываю стоимость каждой пружины. Это слишком медленно для N,Q <= 106, но достаточно для n,q <= 103.
Ответы 1
Общее усилие пружины с начальной длиной x и целевой длиной v пропорционально (x-v)2.
Для группы из N пружин Sum[(xi-v)2] = Sum[xi2] - 2v*Sum[xi] +Nv2
Обратите внимание, что суммирование вообще не зависит от целевой длины, поэтому вы можете просто предварительно вычислить Sum[xi2] и Sum[xi] для всех префиксов вашего массива за время O(n).
Затем для каждого запроса вы можете найти соответствующие суммы и вычислить минимальную стоимость для любого v за время O(1), что в сумме даст O(n+q).
Как вы уже определили, целевая длина минимального усилия — это средняя длина пружины Sum[xi]/N. Это не всегда будет целое число, поэтому просто попробуйте два целых числа по обе стороны от него.
Хотя, если вы действительно хотите применить это к длинам, вы можете сделать это, отслеживая самый большой разрыв в длине и решая, будет ли лучше добавить 10^9+7 к предшествующим ему длинам.
Спасибо за помощь. Я не думал, что решение будет таким простым, и без проблем попробовал использовать решение O(q*log(n)).
Пожалуйста. Обратите внимание, что это традиционный прием расчета текущей дисперсии или стоимости ошибки наименьших квадратов, или с небольшой модификацией, делающий то же самое в скользящем окне. Это вещи, которые вам действительно могут понадобиться в реальной жизни, поэтому полезно знать об этом.
Можем ли мы использовать пространство O(1), если упорядочим запросы и добавим обновления на основе количества обновленных элементов и их суммы? До конца не дочитал, но думаю так.
@גלעדברקן Если вы упорядочиваете запросы, вам не нужно запоминать какие-либо суммы... но вам нужно запомнить все результаты запроса, чтобы вы могли выводить их в правильном порядке. Тогда это не пространство O(1).
Хех, хороший момент!
Применение модуля к ответу — это задание, оставленное читателю.