最小化数组的无序系数（差的绝对值之和）
minimizing disorder coefficient of an array (sum of absolute values of differences)
我遇到了波兰奥林匹克竞赛的一个问题：
每个数组 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| 第一个元素的最小无序系数在与第四个元素交换后得到：|2-4|+|4-5|+|5-7|+|7-5| = 7。我们需要为数组的所有元素计算这个。复杂度应该是 O(nlogN).
只需对您的数组进行排序并计算此排序数组的无序系数。是数组的MDC。
它是如何工作的。
您需要将差异最小的元素放在一起。排序会给出这个结果。
也在努力证明这个理论:)明天更新
我遇到了波兰奥林匹克竞赛的一个问题：
每个数组 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| 第一个元素的最小无序系数在与第四个元素交换后得到：|2-4|+|4-5|+|5-7|+|7-5| = 7。我们需要为数组的所有元素计算这个。复杂度应该是 O(nlogN).
只需对您的数组进行排序并计算此排序数组的无序系数。是数组的MDC。
它是如何工作的。 您需要将差异最小的元素放在一起。排序会给出这个结果。
也在努力证明这个理论:)明天更新