一尘不染

数组中值变换最小步长

algorithm

给定一个具有n个整数的数组A。一轮可以将以下操作应用于任何连续的子数组A [1..r]:分配给子数组A [1..r]的所有A i(l <= i <=
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个元素的排序数组,

由于N的最大值为30,因此我认为要强行强制结果可能会有更好的解决方案。


阅读 234

收藏
2020-07-28

共1个答案

一尘不染

这是Codechef长期竞赛的问题。由于竞赛已经结束,所以尴尬的我贴上了问题解决者的方法(来源:CC竞赛编辑页面)。

“数组的任何状态都可以表示为二进制掩码,每个位1表示对应的数字等于最大值,否则等于0。可以在状态R
[mask]和O(n)过渡的情况下运行DP。可以证明(或者只是相信),如果您运行良好的DP,则statest的数量将不会很大。DP的状态将是等于max的数字的掩码。当然,仅使用运算是有意义的对于这样的子数组[l;
r],1位的数量至少等于子掩码[l;
r]中的0位的数量,因为否则其他情况都不会改变。另外,还应注意,如果您的左边界l操作为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();
}
2020-07-28