Ý tưởng

• Nếu ta có một đoạn ~[L, R]~ thỏa mãn số lượng số chẵn và lẻ bằng nhau, và ta tìm được vị trí ~K \lt R~ sao cho đoạn con ~[L, K]~ có số lượng số chẵn và lẻ bằng nhau, thì ta dễ dàng chứng minh được đoạn ~[K + 1, R]~ cũng có số lượng số chẵn và lẻ bằng nhau.
• Do đó chúng ta sẽ xét hết các vị trí có thể cắt và chọn ra những lần có chi phí thấp nhất để tối ưu số lần cắt.
• Độ phức tạp: ~O(NlogN)~.

Code tham khảo

#include<bits/stdc++.h>
#define reu(i,a,b) for(int i=a,_b=b;i<=_b;++i)
#define red(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define mp make_pair
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define iii pair<int,pair<int,int> >
#define sz(x) int(x.size())
using namespace std;
const int N = 1e5+7;

int n, b, cnt = 0;
ll a[N], ans = 0;
vector <ll> res;

void input()
{
    cin >> n >> b;
    reu(i,1,n) cin >> a[i];
}

void solve()
{
    reu(i,1,n - 1)
    {
        if(a[i] % 2) ++cnt;
        else -- cnt;
        if(cnt == 0) res.pb(abs(a[i] - a[i+1]));
    }
    sort(res.begin(),res.end());
    for(auto &x : res)
    {
        if(b < x) break;
        ++ans;
        b -= x;
    }
    cout << ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();
    return 0;
}