题解 | #小柒的交替数组#

我感觉我的做法在代码实现上比较容易，特此写一篇题解。

从奇偶交替可以想到一些很复杂的分讨做法，但是本质上分类就是区间起始下标的奇偶和数字的奇偶。

因为奇偶转换只需要一次操作，所以只需要关心 的奇偶性即可。不妨就令 表示 是奇数，反之同理，答案肯定是一样的。

可以发现一段区间奇偶交替等价于每个 都跟其下标的奇偶性相同或相反，于是代码非常好写。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+50;
int N,M;
int a[MAXN];
int Sum[MAXN];
int main()
{
	cin>>N>>M;
	for(int i=1;i<=N;i++)
	{
		cin>>a[i];
		a[i]&=1;
		a[i]=(a[i]^(i&1));
	}
	int ans=1e9;
	for(int i=1;i<=N;i++)
	{
		Sum[i]=Sum[i-1]+a[i];
	}
	for(int i=1;i<=N-M+1;i++)
	{
		ans=min(ans,min(Sum[i+M-1]-Sum[i-1],M-(Sum[i+M-1]-Sum[i-1])));
	}
	cout<<ans;
}