小编boy*_*011的帖子

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