Минимизирующий коэффициент беспорядка массива (сумма абсолютных значений разностей)

Question

Я застрял с проблемой из польской олимпиады: каждый массив a1,a2,a3 ... a4 имеет коэффициент беспорядка K, который равен |a[1]-a[2]| + |a[2]- a[3]| + |a[3]-a[4]| ... |a[n-1] -a[n]|, для каждого элемента мы должны вычислить минимальное K, которое может быть достигнуто путем переключения мест с любым другим элементом массива. пример: данный массив 7 4 5 2 5, начальный коэффициент беспорядка для этого массива 10 = |7-4|+|4-5|+|5-2|+|2-5| для 1-го элемента минимальный коэффициент беспорядка достигается после замены его на 4-й: |2-4|+|4-5|+|5-7|+|7-5| = 7, нам нужно рассчитать это для всех элементов массива. сложность должна быть O(nlogN).

Answer 1

Просто отсортируйте ваш массив и рассчитайте коэффициент разброса для этого отсортированного массива. Это MDC массива.

Как это устроено. Вам нужно собрать элементы, разница которых минимальна. Сортировка даст такой результат.

Также пытаюсь доказать эту теорию:) Обновлю завтра.