给定一个包含 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，所以想到了暴力破解的结果 有没有更好的解决方案。
最佳答案
您可以在每次迭代中将包含最大元素的子数组的大小加倍。第一次迭代后，有一个包含最大值的大小为 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:因为这只是在最坏情况下的最佳选择，所以它实际上不是原始问题的答案，它要求找到一种方法来找到所有输入的最少操作数。我将关于暴力破解的句子误解为关于中位数操作的暴力破解，而不是寻找最小操作序列。
关于algorithm - 数组中值变换最小步骤，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10499230/