CF733C[Epidemic in Monstropolis]题解

· · 题解

分析题意：

读题后易得，题意无非是将 a 数组分为连续的 k 段，其中第 i 段的元素和等于 b_i，此后在每段中构造操作序列。

解决代码部分：

分析完题意后，不要着急，分模块写，想清楚自己的思路，同时也方便调试。

1.预处理读入部分：

读入部分没什么好说的，定义 asum,bsum 判断无解情况。

以下为部分代码：

n=read();
for(int i=1;i<=n;i++){
    a[i]=read();
    asum+=a[i];
}
m=read();
for(int i=1;i<=m;i++){
    b[i]=read();
    bsum+=b[i];
}
if(asum!=bsum){ //如果两数组元素和不相等 则无解情况
    puts("NO");
    return 0;
}

2.将 a_i 分为 k 段：

注意一些细节处理，此处变量多，写时要想清楚。有两类无解情况：1.一段区间内元素值全相同，无法吃；2.无法分完，没有完全匹配。

以下为部分代码：

int now=1,nowsum=0,nowmaxx=0,maxxid,pd=a[1],o=1; 
//now记录当前分到了哪一段 nowsum记录当前段中元素和
//nowmaxx记录当前段中区间最值 maxxid记录区间最值位置
//pd表示段中第一个元素 o记录是否区间内数都相同
for(int i=1;i<=n;i++){
    if(nowsum>b[now]){
        puts("NO");return 0;
    }
    nowsum+=a[i];
    if(a[i]>nowmaxx){
        nowmaxx=a[i];
        maxxid=i;
    }
    if(a[i]!=pd)o=0;
    if(nowsum==b[now]){
        ans[now].id=i;
        ans[now].maxx=maxxid;
        if(o==1&&(i-ans[now-1].id)!=1){
            puts("NO");
            return 0;
        }
        now++;
        nowsum=0;
        nowmaxx=0;
        pd=a[i+1];
        o=1;
    }
}
if(now!=m+1){
    puts("NO");
    return 0;
}
else{
    puts("YES");
}

3.输出

注意判断情况，输出时注意判断位置已经改变。因为最大值只记录第一位，所以可以将一段中左边先全吃了。 可有一种特殊情况，如：

4
2 2 2 1
1
7

此时左边没有的吃，右边又吃不了，我们就得将最大值一步步往右移后将右边全吃了后在吃完左边。

以下为部分代码：

for(int i=1;i<=m;i++){
    int flag=0;
    int nm=ans[i].maxx-ans[i-1].id;
    for(int j=ans[i].maxx;j>ans[i-1].id+1;j--){
        printf("%d L\n",i-1+j-ans[i-1].id);
    }
    while(a[ans[i].maxx+1]==a[ans[i-1].id+1]&&a[ans[i].maxx+1]==a[ans[i].maxx]&&(ans[i].maxx+1)<=ans[i].id){
        flag=1;
        ans[i].maxx++;
    }
    if(flag==1){
        for(int j=ans[i].maxx;j<ans[i].id;j++){
            printf("%d R\n",ans[i].maxx-ans[i-1].id+i-1);
        }
        for(int j=ans[i].maxx;j>ans[i-1].id+1;j--){
            printf("%d L\n",i-1+j-ans[i-1].id);
        }
    }
    else{
        for(int j=ans[i].maxx+1;j<=ans[i].id;j++){
            printf("%d R\n",i);
        }
    }
}

完结。