题解 P3558 【[POI2013]BAJ-Bytecomputer】

· · 题解

这题贪心也能做呢！

在机房学长&大佬 @jeffqi 的指导下，用贪心做出来了！。

第一步

首先明确，这个队列只有 0,-1,1 , 并且从始至终最优解都应只有这 3 个数。

假设给出这么一个例子： 

a[3]={1,1,-1}

如果我们要使 a[2]>a[1] , 就需要对 a[2] 进行操作。

  1. 直接用 a[1] 对 a[2] 进行操作 , 需要 2 次操作使 a[2]=1\geq a[1]=1 。

  2. 假设我们花费一步对 a[1] 进行操作使序列变为 \{1,2,-1\} , 然后再对 a[2] 进行操作 , 我们发现我们仍然需要 2 次操作才能使 a[2]=3\geq a[1]=2 ,而再进一步地修改显然也需要更多步数，因此永远保持序列中只存在 1,0,-1 才是性价比最高的做法。

第二步

其次，我们发现，如果队列中只存在 1,0,-1 , 那么很明显这个队列只存在 3 层，即表现为 \{-1,-1,...0,0,...,1,1\} 的形式。那么这其中只存在了 2 个转折点，正常情况下只要枚举这两个转折点就能做出来了，但是这样的做法是 O(n^2) 的，还需要进一步优化。

我们发现，以 0 的序列与以 1 开头的序列都有一些神奇的性质：

对于 1 来说：

如果一个序列(或子序列)以 1 开头，例如下面的情况：

a[6]={1,-1,0,1,-1,0}

我们发现我们无法改变 a[0]=1 的事实，后面的数只能全部变成 1 才能得到正确答案。而此时贪心就排上用场了，我们可以直接把后缀记下来，记录从任意位置开始为 1 时所需的步数，以实现 O(1) 的查找。而记录后缀也是没有任何难度的一次 n 的循环就能搞定的。

对于 0 来说：

如果一个序列(或子序列)以 0 开头，例如下面这 2 组数据：

a1[6]={0,0,-1,-1,1,-1}
a2[6]={0,0,1,0,-1,1}

我们这时已经失去了第一层阶梯，由于第一个数是不允许被改变的，所以我们这时仅允许 0,1 存在

如果我们这时在一串 0 后直接遇到的第 1 个非 0 数字是 -1 的话，我们发现我们拿它没有任何办法，如 a_1[1]=0,a_1[2]=-1 时，无论怎么操作都无法使序列单调不降，这种情况使无解的。

而如果我们遇到的第 1 个非 0 数字是 1 ，此时就可以转化为求以这个 1 所在的位置为起点的子序列的答案，正如上面对 1 所分析的情况一样就可以求出答案了，譬如上面的 a_2 就能转化为一个前面有 2 个 0 而后面子序列以 1 为开头，按后缀查找就可以求出答案了！

所以对于 0 的讨论我们就记下以每一位后的第 1 个非 0 数的位置就可以实现查找了。

对于 -1 来说：

对于 -1 的讨论可以转化为对转折点的讨论。

我们可以直接从前往后扫。如果遇到的是 1 就讨论一下这里是否把 1 变为 0 或 -1，然后比较这 3 种情况下所需的步数并比较大小，记录答案就好了。

而变为 0 和变为 1 的情况都可以用前面的步骤去查找。（碰到无解的时候要特判）

然后再考虑把前面的每一个数都变为 -1 并记录下这样操作的步数然后继续往后扫就能讨论出那些可能的最优解了。而我们发现只用了 O(n) 的时间就查找到了答案！

上代码：

#include<bits/stdc++.h>
#define rep(a,b,c) for(int c=(a);c<=(b);++c)
#define drep(a,b,c) for(int c=(a);c>=(b);--c)
#define INF 0x3f3f3f3f
#define N 1000005
using namespace std;
inline int read()
{
    long long ans=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}
    if(f) return -ans; return ans;
}
int n,a[N],suf[N],nxt[N];
int main()
{
    n=read();int las=n+1;
    rep(1,n,i)a[i]=read();
    drep(n,1,i)
    {
        suf[i]=suf[i+1]+(1-a[i]);
        nxt[i]=las;if(a[i])las=i;
    }
    if(a[1]==1){printf("%d\n",suf[1]);return 0;}
    if(!a[1])
    {
        if(a[nxt[1]]==-1){puts("BRAK");return 0;}
        printf("%d\n",suf[nxt[1]]);return 0;
    }
    int mn=INF,cnt=0;
    rep(1,n,i)
    {
        cnt+=a[i]+1;
        if(a[nxt[i]]!=-1)mn=min(mn,cnt+suf[nxt[i]]);
        if(i<n&&a[i+1]==1)mn=min(mn,cnt+1+suf[nxt[i+1]]);
    }
    printf("%d\n",mn);
}

用时： 64ms

代码长度： 0.9KB 非常好写！