Từ đề bài, ta có thể thấy: một dãy số dễ thương cần đáp ứng đủ ~2~ điều kiện sau: ~\displaystyle\sum_{i=0}^{k-1}a_i\equiv 0\;(\text{mod }2)~ và ~a_i\equiv a_{i-k}\;(\text{mod }2)~, hay nói cách khác, nếu ~p_i\equiv p_j\;(\text{mod }k)~ thì ~a_{p_i}\equiv a_{p_j}\;(\text{mod }2)~.

Ta có thể giải bài toán trên bằng quy hoạch động: gọi ~dp[i][j]~ là số bước thay đổi ít nhất cho ~i~ nhóm đồng dư đầu tiên của ~k~, sao cho tổng của các số đã được xét sẽ đồng dư ~j~ theo mod ~2~.

Ta được công thức quy hoạch động sau: ~dp[i][j] = \text{min}(dp[i - 1][j] + cnt[i][1], dp[i - 1][1 - j] + cnt[i][0])~ với ~cnt[i][j]~ là số vị trí ~p~ thỏa ~p\equiv i\;(\text{mod }k)~ và ~a_{p}\equiv j\;(\text{mod }2)~.

Độ phức tạp: ~O(n)~.

Code mẫu

#include <bits/stdc++.h>
#define BIT(x, i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define TASK ""

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vll;
typedef vector<pll> vlll;

template<typename T1, typename T2> bool mini(T1 &a, T2 b) {if(a>b) a=b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {if(a<b) a=b; else return 0; return 1;}
template<typename T1> T1 abs(T1 a) {if(a<0) a*=-1; return a;}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll h){return l + ll(rd()) * rd() %(h-l+1);}

const int N = 1e6+7;

int n, k;
int cnt[N][2], d[N][2], F[N][2];

int Magic(int i, int h)
{
    if(i==k-1) return cnt[i][h^1];
    if(d[i][h]) return F[i][h]; d[i][h] = 1;
    return F[i][h] = min(Magic(i+1, h) + cnt[i][1], Magic(i+1, h^1) + cnt[i][0]);
}

void proc(const int &TTT)
{
    cin>>n>>k;
    for(int i=0, x; i<n; i++)
    {
        cin>>x;
        cnt[i%k][x%2]++;
    }
    cout<<Magic(0, 0);
}

int main()
{
//    freopen(TASK".inp", "r", stdin);
//    freopen(TASK".out", "w", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    int numTest = 1; //cin>>numTest;
    for(int i=1; i<=numTest; i++) proc(i);
    return 0;
}