Дан массив A[n] (длина n) неотрицательных целых чисел. Массив содержит n объектов, рассредоточенных внутри себя, так что A[i] представляет количество объектов в слоте i, а сумма A[i] от i=0 до n равна n . Мы должны переупорядочить массив так, чтобы каждый элемент был равен 1. Нам дано, что n ‹= 10^5. (Поэтому O(n^2) слишком медленный, но O(n log n) в порядке.)
Перестановка работает следующим образом: если A[i] = k и A[j] = h, то мы можем уменьшить A[i] на некоторое натуральное число m ‹= k и увеличить некоторый элемент A[j] на m соответственно, так что A[i] = k-m и A[j] = h+m. Однако стоимость каждой перестановки определяется выражением Cost(m, i, j) = m d(i, j)^2 (пропорционально квадрату расстояния перестановки). Массив работает таким образом, что функция расстояния d(i, j) представляет собой стандартное вычитание, но может охватывать массив, поэтому, если n = 7, то d(1, 4)=3, но d(0, 6) = 1 и d(1,5) = 3 и т. д. То есть мы можем думать о массиве как о «круговом».
Общая стоимость определяется суммой функции стоимости по всем перестановкам, и наша цель — найти минимальное значение функции стоимости, такое что A[i] = 1 для всех i, т. е. все элементы равны 1. Каждый объект можно переставить только один раз, например, если A = [5,0,0,0,0], мы не можем просто переместить объект из A[0] в A[1], а затем в A[2]. чтобы обойти квадрат расстояния.
Будем признательны за помощь в алгоритме или псевдокоде/коде для решения этой проблемы.
