12

配列内の各項目について、[-K、K] に数値を加算または減算すると厳密に昇順の配列になるように、正の最小数 K を見つける方法は?

例えば：

  • 配列は[10、2、20]です
  • 最小 K は 5 であり、考えられる結果は [10-5, 2+4, 20] です。
  • 10-4 == 2+4 であるため、k = 4 は OK ではありません。配列を厳密な昇順に変換することはできません

私の推測は次のとおりです

define f(i, j) = a[i] - a[j] + ji-1 (i < j および a[i] > a[j] に必要: すべての逆順のペア)

最小 K は次の条件を満たす必要があります。

2*K > 最大 f(i,j)

ペア (i, j) が昇順でない場合、a[j] は最大で K しか加算できず、a[i] は最大で K を減算でき、a[i] とa[j] (厳密に昇順であるため)、(a[j] + K) - (a[i] - K) は (ji-1) (それらの間の長さ) より大きくなければなりません。

したがって、k >= 最大 f(i, j)/2 + 1

問題は、k = max f(i, j)/2 + 1 が OK かどうかを証明できないことです。

より多くの手がかり:

特定の K が十分かどうかを判断するアルゴリズムを見つけることを考えました。次に、アルゴリズムを使用して、可能な最小値から各 K を試して解を見つけることができます。

私は次のようなアルゴリズムを思いつきました：

for i in n->1  # n is array length
if i == n:
    add K to a[i]   # add the max to the last item won't affect order
else:
    # the method is try to make a[i] as big as possible and still < a[i+1]
    find a num k1 in [-K, K] to make a[i] to bottom closest to a[i+1]-1
    if found:
        add k1 to a[i]
    else no k1 in [-K, K] can make a[i] < a[i+1]
        return false
return true

私もそのようなアルゴリズムが正しいかどうか

4

2 に答える 2

11

あなたの推測は正しいと思いますが、それを証明することもできません:-)代わりに、質問を単純化することから始めます

配列内の各項目について、[-K、K] に数値を加算または減算すると厳密に昇順の配列になるように、正の最小数 K を見つける方法は?

Kを「追加」することにより、この同等のものに：

配列内の各項目に [0, 2*K] からの数値を追加すると、厳密に昇順の配列になるような、正の最小数 2*K を見つける方法は?

これは、配列を反復処理し、条件を満たすために必要な 2K 値を追跡することで、非常に簡単に解決できます。@ruakhのものと非常に似ていますが、減算はありません：

k2 = 0
last = arr[0]
for each cur in arr from 1
    if cur + k2 <= last
        last ++
        k2 = last - cur
    else
        last = cur
k = ceil ( k2 / 2 )
于 2013-09-29T09:52:36.027 に答える
8

あなたはこれを少し考えすぎていると思います。配列の要素を反復処理して、 Kの現在の最小可能値と、そのKの値が与えられたときに最後に表示された要素の現在の最小可能値を追跡できます。Kが小さすぎることを証明する要素が見つかった場合は、それに応じてそれを増やすことができます。

たとえば、Java では次のようになります。

int[] array = { 10, 2, 20 };
int K = 0, last = array[0];
for (int i = 1; i < array.length; ++i) {
    if (last >= array[i] + K) {
        // If we're here, then our value for K wasn't enough: the minimum
        // possible value of the previous element after transformation is still
        // not less than the maximum possible value of the current element after
        // transformation; so, we need to increase K, allowing us to decrease
        // the former and increase the latter.
        int correction = (last - (array[i] + K)) / 2 + 1;
        K += correction;
        last -= correction;
        ++last;
    } else {
        // If we're here, then our value for K was fine, and we just need to
        // record the minimum possible value of the current value after
        // transformation. (It has to be greater than the minimum possible value
        // of the previous element, and it has to be within the K-bound.)
        if (last < array[i] - K) {
            last = array[i] - K;
        } else {
            ++last;
        }
    }
}
于 2013-09-29T09:25:27.767 に答える