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

Question

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

现在，如何在转换列表时将总成本降到最低？

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

附言:

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 是排序列表的最小值和最大值。其他情况同理。

每个解决方案都由分配给第一个元素的编号定义。如果这个数字非常小，那么将它增加一个将降低成本。我们可以继续增加这个数字，直到成本增加。从这一点来看，成本将不断增长。所以最优值将是局部最小值，我们可以使用二进制搜索找到它。我们要搜索的范围将是 [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