2

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

现在，如何在如上所述转换列表时最小化总成本？

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

PS：

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

这是Topcoder 问题的一个子部分。

4

2 回答 2

4

让我们假设解决方案是按递增顺序排列的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
于 2015-03-23T15:16:48.643 回答
1

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

  1. 让我们假设这些数字是x, x + 1, x + n - 1。那么成本是sum i = 0 ... n - 1 of abs(a[i] - (x + i))。让我们称之为f(x)。

  2. f(x)是分段线性的，它随着x接近+infinity或接近无穷大-infinity。这意味着在端点之一达到其最小值。

  3. 终点是a[0], a[1] - 1, a[2] - 2, ..., a[n - 1] - (n - 1)。所以我们可以尝试所有这些并选择最好的。

于 2015-03-23T14:35:04.853 回答