algorithm - 给定k个已排序的数字，将它们变成连续数字的最小成本是多少？

Question

假设我们得到了一个包含 k 个数字的排序列表。现在，我们想要将这个排序列表转换为具有连续数字的列表。唯一允许的操作是我们可以将数字增加/减少 1。执行每一次这样的操作都会导致总成本增加一倍。

现在，如何在如上所述转换列表时最大限度地降低总成本？

我的一个想法是获取排序列表的中位数，并将数字排列在中位数周围。之后只需添加新创建的列表中对应数字与原始列表中对应数字之间的绝对差即可。但是，这只是一种直观的方法。我没有任何证据。

附注:

Here's an example-
Sorted list: -96, -75, -53, -24.
We can convert this list into a consecutive list by various methods. 
The optimal one is: -58, -59, -60, -61
Cost: 90

这是 problem from Topcoder 的子部分.

Answer 1

假设解按升序排列，并且 m、M 是排序列表的最小值和最大值。其他情况同样处理。

每个解决方案均由分配给第一个元素的编号定义。如果这个数字非常小，那么将其增加 1 将降低成本。我们可以继续增加这个数字，直到成本增加。从这一点来看，成本将不断增长。因此最优值将是局部最小值，我们可以使用二分搜索找到它。我们要搜索的范围为[m - n, M + n]，其中n是元素数量:

l = [-96, -75, -53, -24]

# Cost if initial value is x
def cost(l, x):
    return sum(abs(i - v) for i, v in enumerate(l, x))

def find(l):
    a, b = l[0] - len(l), l[-1] + len(l)
    while a < b:
        m = (a + b) / 2
        if cost(l, m + 1) >= cost(l, m) <= cost(l, m - 1): # Local minimum
            return m
        if cost(l, m + 1) < cost(l, m):
            a = m + 1
        else:
            b = m - 1
    return b

测试:

>>> initial = find(l)
>>> range(initial, initial + len(l))
[-60, -59, -58, -57]
>>> cost(l, initial)
90