2

k個の数字のソートされたリストが与えられたとします。次に、このソートされたリストを連続した番号を持つリストに変換します。許可されている唯一の操作は、数値を 1 ずつ増減できることです。このような操作をすべて実行すると、総コストが 1 増加します。

さて、前述のようにリストを変換しながら、総コストを最小限に抑えるにはどうすればよいでしょうか?

私が持っている 1 つのアイデアは、並べ替えられたリストの中央値を取得し、中央値の周りに数字を配置することです。その後、新しく作成されたリストと元のリストの対応する番号の絶対差を追加するだけです。しかし、これはあくまでも直感的な方法です。私はそれの証拠を持っていません。

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がソートされたリストの最小値と最大値であると仮定しましょう。もう一方のケースも同様に処理されます。

各ソリューションは、最初の要素に割り当てられた番号によって定義されます。この数が非常に小さい場合は、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
于 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ます。これは、エンドポイントの 1 つでその最小値に達したことを意味します。+infinity-infinity

  3. エンドポイントはa[0], a[1] - 1, a[2] - 2, ..., a[n - 1] - (n - 1). したがって、それらすべてを試して、最高のものを選ぶことができます。

于 2015-03-23T14:35:04.853 に答える