给定一个包含 n 个整数的数组 A。在一个回合中，可以将以下操作应用于任何连续的子数组 A[l..r] ：分配给子数组 A[l..r] 的所有 A i (l <= i <= r) 中位数。令 max 为 A 的最大整数。我们想知道将 A 更改为由 n 个整数组成的数组所需的最小操作数，每个整数的值为 max。例如，让 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 个元素的排序数组，
由于 N 的最大值是 30。我想暴力破解结果可能有更好的解决方案。
您可以在每次迭代中将包含最大元素的子数组的大小加倍。在第一次迭代之后，有一个大小为 2 的子数组包含最大值。然后将您的操作应用于包含这两个元素的大小为 4 的子数组，为您提供包含最大值的大小为 4 的子数组。然后应用于大小为 8 的子数组，依此类推。您在 log2(N) 操作中填充数组，这是最佳的。如果 N 为 30，则五次操作就足够了。
这在最坏的情况下（即只有一个元素是最大值时）是最佳的，因为它在每次迭代中设置了尽可能多的元素。
更新 1：我注意到我把 4s 和 8s 搞砸了。已更正。
更新 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：由于这仅在最坏的情况下是最佳的，因此它实际上不是原始问题的答案，它要求找到一种方法来找到所有输入的最小操作数。我将关于暴力破解的句子误解为关于中间操作的暴力破解，而不是找到最小的操作序列。
这是 codechef Long Contest 的问题。由于比赛已经结束，所以很尴尬，我正在粘贴问题设置器方法（来源：CC Contest 编辑页）。
“数组的任何状态都可以表示为二进制掩码，每个位 1 表示对应的数字等于最大值，否则为 0。您可以使用状态 R[掩码] 和 O(n) 转换运行 DP。您可以证明（或者只是相信）statest 的数量不会很大，当然如果你运行良好的 DP。我们的 DP 的状态将是等于 max 的数字的掩码。当然，仅使用操作是有意义的对于这样的子数组 [l; r]，1 位的数量至少与子掩码 [l;r] 中的 0 位的数量一样多，因为否则什么都不会改变。另外你应该注意到，如果你的左边界"
C/C++ 代码是::
#include <cstdio>
#include <iostream>
using namespace std;
int bc[1<<15];
const int M = (1<<15) - 1;
void setMin(int& ret, int c)
{
if(c < ret) ret = c;
}
void doit(int n, int mask, int currentSteps, int& currentBest)
{
int numMax = bc[mask>>15] + bc[mask&M];
if(numMax == n) {
setMin(currentBest, currentSteps);
return;
}
if(currentSteps + 1 >= currentBest)
return;
if(currentSteps + 2 >= currentBest)
{
if(numMax * 2 >= n) {
setMin(currentBest, 1 + currentSteps);
}
return;
}
if(numMax < (1<<currentSteps)) return;
for(int i=0;i<n;i++)
{
int a = 0, b = 0;
int c = mask;
for(int j=i;j<n;j++)
{
c |= (1<<j);
if(mask&(1<<j)) b++;
else a++;
if(b >= a) {
doit(n, c, currentSteps + 1, currentBest);
}
}
}
}
int v[32];
void solveCase() {
int n;
scanf(" %d", &n);
int maxElement = 0;
for(int i=0;i<n;i++) {
scanf(" %d", v+i);
if(v[i] > maxElement) maxElement = v[i];
}
int mask = 0;
for(int i=0;i<n;i++) if(v[i] == maxElement) mask |= (1<<i);
int ret = 0, p = 1;
while(p < n) {
ret++;
p *= 2;
}
doit(n, mask, 0, ret);
printf("%d\n",ret);
}
main() {
for(int i=0;i<(1<<15);i++) {
bc[i] = bc[i>>1] + (i&1);
}
int cases;
scanf(" %d",&cases);
while(cases--) solveCase();
}
问题制定者方法具有指数复杂性。N = 30 非常好。但对于更大的尺寸，情况并非如此。我认为，找到指数时间解决方案更有趣。我找到了一个，复杂度为 O(N 4 )。
这种方法利用了这样一个事实，即最优解从一组连续的最大元素开始，并且只扩展这一个组，直到整个数组被最大值填充。
为了证明这一事实，取 2 个连续最大元素的起始组，并以最佳方式扩展它们中的每一个，直到它们合并为一个组。假设第 1 组需要 X 轮才能增长到 M 大小，第 2 组需要 Y 轮才能增长到相同大小 M，并且在轮 X + Y + 1 时这些组合并。结果是一组大小至少为 M * 4。现在不是为第 2 组转 Y，而是为第 1 组额外转 X + 1。在这种情况下，组大小至少为 M * 2，最多为 M / 2 （即使我们最初计算最大元素，也可能包含在步骤 Y 中）。在此更改之后，在第 X + Y + 1 轮，合并组大小至少为 M * 4，仅作为第一个组扩展的结果，从第二组中添加至少一个元素。因此，在这里扩展单个组会以相同的步数产生更大的组（如果 Y > 1，它甚至需要更少的步骤）。由于这适用于相等的组大小 (M)，因此对于不相等的组会更好。这个证明可以扩展到多组（多于两个）的情况。
要处理单组连续最大元素，我们只需要跟踪两个值：组的开始位置和结束位置。这意味着可以使用三角矩阵来存储所有可能的组，从而允许使用动态规划算法。
For each group of consecutive maximal elements in original array:
Mark corresponding element in the matrix and clear other elements
For each matrix diagonal, starting with one, containing this element:
For each marked element in this diagonal:
Retrieve current number of turns from this matrix element
(use indexes of this matrix element to initialize p1 and p2)
p2 = end of the group
p1 = start of the group
Decrease p1 while it is possible to keep median at maximum value
(now all values between p1 and p2 are assumed as maximal)
While p2 < N:
Check if number of maximal elements in the array is >= N/2
If this is true, compare current number of turns with the best result \
and update it if necessary
(additional matrix with number of maximal values between each pair of
points may be used to count elements to the left of p1 and to the
right of p2)
Look at position [p1, p2] in the matrix. Mark it and if it contains \
larger number of turns, update it
Repeat:
Increase p1 while it points to maximal value
Increment p1 (to skip one non-maximum value)
Increase p2 while it is possible to keep median at maximum value
while median is not at maximum value
为了保持算法简单，我没有提到组从位置 0 开始或在位置 N 结束时的特殊情况，跳过初始化并且没有进行任何优化。