AWOI R2 C 数组操作

· · 题解

显然地，若要对 c_x 进行变换操作，要分类讨论：当 c_x \ne y 时，为了更快的接近目标状态，一定会将 c_x 改成 y；当 c_x=y 时，c_x 一定会被改为一个不为 y 的值。

所以，我们将数组中等于 y 的元素染成红色，将不等于 y 的元素染成蓝色。变换操作就相当于选择一个区间，将区间内的蓝色变为红色，红色变为蓝色。而目标就变为了将数组全部变为红色。

for(int i=1; i<=n; i++) a[i]=(read()==y);//true 表示红，false 表示蓝
for(int i=1; i<=n; i++) b[i]=(read()==y);//同上

先不考虑翻转操作和如何合并，假设合并后 c 数组染色后如图，考虑这种情况下最少需要多少次操作达到目标状态。

容易发现，这张图至少需要 4 次操作才能达到目标，即将所有蓝色段变为红色。推广到更一般的情况，我们可以发现，最小的操作次数就是蓝色段的个数。

我们先考虑如何让数组 a,b 合并后满足合并要求并统计出蓝色段个数。为了最小化操作次数，就要让蓝色段的数量最少，合并时应该让尽量多的蓝元素挨在一块，让尽量多的红元素挨在一块。

可以发现，执行以下两种操作若干次直到 a,b 为空，可以满足要求：

意识到这点，我们就得到思路了：

  1. 将初始颜色段设为红色段。因为红色在前可以让更多的蓝色挨在一起。
  2. 若当前段是蓝色段，蓝色段计数器 s\gets s+1。
  3. 找到 a 数组的前缀有多少个与该颜色段颜色相同，全部放入 c 数组。
  4. 找到 b 数组的前缀有多少个与该颜色段颜色相同，全部放入 c 数组。
  5. 变换为下一段颜色，重复第 2 步。

最终，s 就是合并后最小的蓝色段数量。

bool now=true;
int c1=0,c2=0,s=0;
while(1){
    if(!now) s++;
    while(a[c1+1]==now && c1+1<=n) c1++;
    while(b[c2+1]==now && c2+1<=n) c2++;
    if(c1==n && c2==n) break;
    now=!now;
}

最优的合并策略已考虑，现在考虑最优翻转策略。由于答案是蓝色段的个数，所以翻转操作要让蓝色段数量减少。

我们选择一个红色段的左端点为 l，与其相邻蓝色段的右端点为 r，将 [l,r] 翻转，就可以减少一个蓝色段了。

于是，我们可以发现，每一次的翻转都可以减少一个蓝色段！因此，若需要翻转的次数 s-1\geqslant z，只需尽可能减少蓝色段，即翻转 z 次。答案就是 s-z。

有人可能有疑问：如果翻转到只剩一个蓝色段后（需要 s-1 次），翻转次数小于 z（即 s-1<z）怎么办？其实，可以直接进行变换操作将其全部变为红色，答案为 1，再不停翻转整个区间 [1,2n]。

还有一种特殊情况，就是输入的所有元素都是红元素（s=0），直接输出 0 即可。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;
bool a[N],b[N];

char *p1,*p2,buf[100000];
#define r() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read(){
    int x=0,f=1;
    char ch=r();
    while(ch<48||ch>57){
        if(ch=='-') f=-1;
        ch=r();
    }
    while(ch>=48 && ch<=57) x=x*10+ch-48,ch=r();
    return x*f;
}

int main(){
    int n=read(),y=read(),z=read();
    for(int i=1; i<=n; i++) a[i]=(read()==y);
    for(int i=1; i<=n; i++) b[i]=(read()==y);
    bool now=true;
    int c1=0,c2=0,s=0;
    while(1){
        if(!now) s++;
        while(a[c1+1]==now && c1+1<=n) c1++;
        while(b[c2+1]==now && c2+1<=n) c2++;
        if(c1==n && c2==n) break;
        now=!now;
    }
    if(!s) cout<<0;
    else if(s-1>=z) cout<<s-z;
    else cout<<1;
    return 0;
}