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

Question

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

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

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

P.S.:

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

这是一个简单的解决方案：

我们假设这些数字是x, x + 1, x + n - 1。那么成本就是sum i = 0 ... n - 1 of abs(a[i] - (x + i))。我们称它为 f(x).
f(x) 是分段线性的，当 x 接近 +infinity 或 -infinity 时它接近无穷大。这意味着在其中一个端点达到了它的最小值。
终点是a[0], a[1] - 1, a[2] - 2, ..., a[n - 1] - (n - 1)。所以我们可以尝试所有这些并选择最好的。

Answer 2

让我们假设解决方案是按升序排列的，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

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

Given k sorted numbers, what is the minimum cost to turn them into consecutive numbers?

sorting

algorithm

contiguous