数组中位数转换最小步骤

Question

数组中位数转换最小步骤

5

给定一个具有 n 个整数的数组 A。在一次操作中，可以将以下操作应用于任何连续子数组 A[l..r] : 将A i (l <= i <= r) 中所有元素赋值为子数组A[l..r]的中位数。让max 是 A 的最大整数。我们想知道需要多少最小操作来将 A 改变为具有值 max 的 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个元素的排序数组，中位数是第3个元素，而对于具有6个元素的排序数组，它是第4个元素。

由于 N 的最大值为30，我想到了暴力破解结果，但是否有更好的解决方案？

- mvpd

需要进行最少的操作来改变什么？给定的数组，还是任何给定大小的数组？ - n. m.

@n.m.，显然，这是一个给定的数组。因为对于任何数组，在最坏情况下，最小数字总是ceil(log N))。 - Evgeny Kluev

@Evgeny：也许那是预期的答案。或者可能是其他什么。你可以查看数组元素吗？ - n. m.

对于数组 2 1 1 2 的一些示例，答案将是 1。对于数组 4 4 4 4 4，答案将是 0。 - mvpd

3个回答

2

这是来自codechef长竞赛的问题。由于比赛已经结束，所以我会粘贴出题人的解决方案（来源：CC Contest Editorial Page）。

“数组的任何状态都可以表示为二进制掩码，其中每个位1表示相应的数字等于最大值，否则为0。您可以使用状态R [mask]和O（n）转换运行DP。您可以证明（或只是相信），如果您运行良好的DP，则状态数不会很大。我们DP的状态将是等于最大值的数字的掩码。当然，仅对1位数至少与子掩码[l; r]中的0位数相同的此类子数组[l; r]使用操作才有意义，因为否则不会发生任何变化。此外，您还应该注意，如果您的操作左边界是l，则最好仅使用最大可能的r进行操作（这使得转换次数等于O（n））。对于C ++编码人员来说，使用映射结构来表示所有状态也很有用。”

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();
}

- Ritesh Kumar Gupta

1

我还建议您浏览此页面。http://www.codechef.com/wiki/may-2012-contest-problem-editorials - Ritesh Kumar Gupta

1

问题设置器方法具有指数复杂度。对于N=30来说还不错，但对于更大的尺寸就不太适用了。我认为，找到一个指数时间解决方案更有趣。我找到了一个O(N^4)复杂度的解决方案。

这种方法利用了最优解始于一些连续的最大元素组，并且仅扩展这个单一组，直到整个数组填满最大值的事实。

为了证明这个事实，我们取两个起始连续最大元素组，并将它们以最优方式扩展，直到它们合并成一个组。假设第一组需要X轮才能增长到大小M，第二组需要Y轮才能增长到相同的大小M，在第X+Y+1轮时这些组合并。结果是一个大小至少为M*4的组。现在，不要让第二组进行Y轮，而是让第一组进行额外的X+1轮。在这种情况下，即使我们计算最初可能包含在步骤Y中的最大元素，组大小也至少为M*2，最多为M/2。在这种改变后，在第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结束时的特殊情况，跳过了初始化并且没有进行任何优化。

- Evgeny Kluev

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- njlarsson · Accepted Answer

在每次迭代中，您可以将包含最大元素的子数组的大小加倍。第一次迭代后，存在一个包含最大值的大小为2的子数组。然后将操作应用于包含这两个元素的大小为4的子数组，从而得到一个包含最大值的大小为4的子数组。然后应用于大小为8的子数组等等。您需要log2（N）次操作填充数组，这是最优的。如果N为30，则仅需五次操作。

在最坏情况下（即仅有一个元素是最大值），这是最优的，因为它在每次迭代中设置了最高可能数量的元素。

更新1：我注意到我有点混淆了4和8。已更正。

更新2：这里有一个例子。数组大小为10，起始状态：

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

要获取两个九，请在包含两个九的子数组上运行op。例如，A[4…5] 可以得到以下结果：

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

现在运行包含4…5的四个大小的子数组，例如在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：由于这种方法只在最坏情况下达到最优，实际上它并不是原问题的答案，原问题是要找到所有输入的最小操作次数。我误解了有关暴力破解的句子，认为是指用中间操作的蛮力破解，而不是找到操作序列的最小值。