题目描述
给定两个长度为 \(n\) 的数组 \(a,b\) ，将它们合并得到一个长度为 \(2\times n\) 的数组 \(c\)。
设 \(a\) 数组第 \(i\) 个元素合并后位于 \(c\) 数组第 \(lb_i\) 个位置，\(b\) 数组第 \(i\) 个元素合并后位于 \(c\) 数组第 \(lc_i\) 个位置，合并后需要满足：\(lb_1 < lb_2 < ...< lb_{n-1} < lb_n\) 且 \(lc_1 < lc_2< ...< lc_{n-1}< lc_n\)，即两个数组中元素的相对位置不变。
合并过后，你需要对 \(c\) 数组进行下面操作：
- 变换操作：选择一个区间 \([l,r]\)，对于每一个 \(i \in [l,r]\)，如果 \(c_i\) 为 \(y\)，则将其变成一个不同于 \(y\) 的数，否则将其变为 \(y\)。
- 翻转操作：选择一个区间 \([l,r]\)，翻转该数组区间中的数。此操作必须刚好操作 \(z\) 次。
请输出最少需要执行多少次变换操作才能使得 \(c\) 数组中的数字都为 \(y\)。
输入格式
第一行包含三个整数 \(n,y,z\)。
第二行包含 \(n\) 个整数，代表 \(a\) 数组中的元素。
第三行包含 \(n\) 个整数，代表 \(b\) 数组中的元素。
输出格式
一个正整数，表示答案。
样例输入
5 1 1
1 1 45 1 4
1 9 1 9 810
样例输出
1
提示
对于全部数据，保证 \(0 \leqslant y,z \leqslant 10^9\)，输入数据全部在 int 范围内。
由于合并出来的 \(c\) 数组不会改变数之间的相对位置，所以先研究 \(c\) 数组。
对于 \(c\) 数组分为两个部分，一部分是等于 \(y\) 的，一部分是不等于的。
如果不考虑翻转，现在所需要的变换操作就是不等于 \(y\) 的连续段的个数。
举个例子，我们知道样例一最后的 \(c\) 数组为 \({1,1,1,9,45,1,1,9,4,810}\)，那么变换操作就是两次。
要让操作数尽可能小，就需要使用翻转操作，对于每一次翻转，可以把等于 \(y\) 的子段和与之相邻的不等于 \(y\) 的子段进行翻转，这样便可以把两个不等于 \(y\) 的子段拼在一起，从而减少一次操作，而 \(z\) 次翻转最多便可以减少 \(z\) 次操作。
接着考虑如何拼出一个 \(c\) 数组，根据上面的分析，很容易看出我们需要尽可能让等于 \(y\) 的子段在一起，而又不能破坏相对位置。
双指针可以搞定。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,y,z;
const int N=1e6+5;
int a[N],b[N];
signed main()
{
scanf("%lld%lld%lld",&n,&y,&z);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
int i=1,j=1;
int flag=1,sum=0;
while(i<=n||j<=n){
if(flag==0) sum++;
while((a[i]==y)==flag&&i<=n) i++;
while((b[j]==y)==flag&&j<=n) j++;
flag^=1;
}
if(!sum) return printf("0"),0;//特判，如果根本就没有不等于y的部分，直接返回0
if(sum>z) return printf("%lld",sum-z),0;
printf("1");
return 0;
}