如何求数组的最小正数K使数组严格升序
如何求数组的最小正数K使数组严格升序
提问于 2013-09-29 08:45:49
如何找到最小正数K，以便对于数组中的每一项，从-K中加或减一个数字，K可以导致严格的升序数组？
例如：
- 数组是10，2，20
- 最小K为5，可能的结果是10-5，2+4，20。
- K=4不确定，因为10-4 == 2+4；不能将数组转换为严格的升序。
我的猜测如下
定义f(i，j) = ai - aj + j-i-1 (i aj要求:所有反向序对)
最小K必须满足以下条件：
2*K > max f(i，j)
因为如果一对(i，j)不是升序，aj最多只能添加K，ai最多可以减去K，并且您需要在ai和j之间为项留出空间，所以(aj + K) - (ai - K)应该大于(j-i-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我也是这样一个算法对不对
回答 2
Stack Overflow用户
发布于 2013-09-29 09:52:36
我认为你的猜测是正确的，但我也无法证明这一点:-)相反，我首先要简化你的问题
如何找到最小正数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 )Stack Overflow用户
发布于 2013-09-29 09:25:27
我觉得你想得有点过头了。只要迭代数组中的元素，跟踪当前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;
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19076096
复制相关文章
相似问题
腾讯云开发者
