12

如何找到最小正数 K 使得对于数组中的每个项目，从 [-K, K] 中添加或减去一个数字可以导致一个严格升序的数组？

例如：

  • 数组是 [10, 2, 20]
  • 最小 K 为 5，可能的结果是 [10-5, 2+4, 20]
  • k = 4 不行，因为 10-4 == 2+4；数组不能转换为严格的升序

我的猜测如下

定义 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 >= max f(i, j)/2 + 1

问题是我无法证明 k = max f(i, j)/2 + 1 是否可以？

更多线索：

我已经考虑过找到一种算法来确定给定的 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 到这个等价的：

如何找到最小正数 2*K 使得对于数组中的每个项目，从 [0, 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 回答