如何找到数组的最小正数K以使数组严格按升序排列

Question

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

例如:

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

---

我的猜测如下

define f(i,j)= a [i] - a [j] + ji-1(要求i <j和a [i]> a [j]:所有逆序对)

最小K必须满足条件:

2*K> max f(i,j)

因为如果一对(i,j)不是按升序排列,[j]最多只能加K,a [i]最多可以减去K,你需要在[i]和[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

我也是这样的算法是对还是不对

Answer 1

我认为你的猜测是正确的,但我无法证明这一点:-)相反,我会先简化你的问题

如何找到最小正数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 )

Answer 2

我想你有点过分思考了.您可以迭代数组的元素,跟踪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;
        }
    }
}