自动搬运

查看原文

来自洛谷，原作者为

	Vct14 **

搬运于2025-08-24 22:49:22，当前版本为作者最后更新于2023-08-11 13:18:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

显然地，若要对 $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$ 为空，可以满足要求：

• 取出 $a$ 的前缀的若干个元素放入 $c$ 数组（后方元素向前移）。
• 取出 $b$ 的前缀的若干个元素放入 $c$ 数组（后方元素向前移）。

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

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