[CF1092D1] Great Vova Wall - 栈,贪心

Description

给定一个序列 \(a=\{a_1,a_2,\dots,a_n\}\)，有以下两种操作：若 \(a_i=a_{i+1}\)，则可将 \(a_i\) 与 \(a_{i+1}\) 同时加 \(1\)；将 \(a_i\) 加 \(2\)。求问是否可经过多此操作后使得所有 \(a_i\) 相等。

Solution

相当于按奇偶性做匹配，不难想到用栈维护，碰到奇偶性相同的就消去，如果最后栈内剩余元素数量不超过 1 则 YES

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> s(n + 2);
    int top = 0;
    for (int i = 1; i <= n; i++)
    {
        s[++top] = a[i] & 1;
        if (top > 1 && s[top] == s[top - 1])
            top -= 2;
    }
    cout << (top <= 1 ? "YES" : "NO") << endl;
}