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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll m,n;
    cin>>n>>m;
    ll arr[n+1]={0};
    for(ll i=1;i<=n;i++)                   //将数组转换为只包含0和1
    {
        cin>>arr[i];
        if(arr[i]&1)
            arr[i]=1;
        else
            arr[i]=0;
    }
    ll dp[n+1]={0},sum[n+1]={0};            //由于只有010101和101010两种结果，所以用这两种结果创   
    for(ll i=1;i<=n;i++)                    //两个前准缀和数组来统计两种结果的修改次数
    {
        sum[i]+=sum[i-1];
     if(i&1&&arr[i]==0)
     {
         sum[i]++;
     }
        else if(i%2==0&&arr[i]==1)
        {
            sum[i]++;
        }
    }
    for(ll i=1;i<=n;i++)
    {
        dp[i]+=dp[i-1];
     if(i%2==1&&arr[i]==1)
     {
         dp[i]++;
     }
        else if(i%2==0&&arr[i]==0)
        {
            dp[i]++;
        }
    }
    ll res=9999999999;                                //遍历所有的M子区间，统计更新最小值
    for(ll i=1;i<=n-m+1;i++)
    {
        ll a=sum[i+m-1]-sum[i-1];
        ll b=dp[i+m-1]-dp[i-1];
        res=min(min(a,b),res);                          //先计算两个前缀和数组最小再相继比较
    }
    cout<<res<<endl;
    return 0;
}