algorithm - 数组中值变换最小步骤

Question

给定一个包含 n 的数组 A整数。在一个回合中，一个人可以应用以下操作到任何连续子数组 A[l..r] :分配给所有 A i (l <= i <= r)子数组 A[l..r] 的中位数。令 max 为 A 的最大整数。我们想知道最低限度改变 A 所需的操作数到 n 个整数的数组，每个整数都有值最大限度。例如，让 A = [1, 2, 3] 。我们想将其更改为 [3, 3, 3] 。我们可以通过两个操作来做到这一点，首先是子数组 A[2..3](之后 A 等于 [1,3, 3] ), 然后操作到 A[1..3] 。此外，中位数是为某些数组 A 定义的，如下所示。让B相同数组 A ，但按非递减排序命令。 A 的中位数是 B m(基于 1索引)，其中 m 等于 (n div 2)+1 。这里'div'是整数除法运算。因此，对于具有 5 个元素的排序数组，中位数是第三个元素，对于排序有 6 个元素的数组，它是第 4 个元素。

由于N的最大值是30，所以想到了暴力破解的结果有没有更好的解决方案。

Answer 1

您可以在每次迭代中将包含最大元素的子数组的大小加倍。第一次迭代后，有一个包含最大值的大小为 2 的子数组。然后将您的操作应用于包含这 2 个元素的大小为 4 的子数组，从而为您提供包含最大值的大小为 4 的子数组。然后应用于大小为 8 的子数组，依此类推。您在 log2(N) 操作中填充数组，这是最佳的。如果 N 为 30，则五次操作就足够了。

这在最坏的情况下是最优的(即当只有一个元素是最大值时)，因为它在每次迭代中设置了尽可能多的元素。

更新 1:我注意到我把 4 和 8 弄乱了一点。更正。

更新 2:这是一个示例。数组大小 10，开始状态:

[6 1 5 9 3 2 0 7 4 8]

要获得两个 9，请对包含 9 的大小为 2 的子数组运行 op。例如 A[4…5] 得到你:

[6 1 5 9 9 2 0 7 4 8]

现在在包含 4…5 的大小为 4 的子数组上运行，例如在 A[2…5] 上运行以获得:

[6 9 9 9 9 2 0 7 4 8]

现在在大小为 8 的子数组上，例如 A[1…8]，得到:

[9 9 9 9 9 9 9 9 4 8]

现在加倍会得到 16 个 9，但我们只有 10 个位置，所以用 A[1…10] 进行一轮，得到:

[9 9 9 9 9 9 9 9 9 9]

更新 3:因为这只是在最坏情况下的最佳选择，所以它实际上不是原始问题的答案，它要求找到一种方法来找到所有输入的最少操作数。我将关于暴力破解的句子误解为关于中位数操作的暴力破解，而不是寻找最小操作序列。