题解 奇变偶不变

Kedit2007 · 2022-06-02 19:51:28 · 题解

题目链接

思路

我们知道，若两个数都是奇数或偶数，它们的和是偶数。若两个数奇偶不一致，则和为奇数。

那么我们要做的操作就是让序列中所有相邻的元素奇偶一致。也就是让序列中只有奇数或只有偶数。

达到这个目的很简单，只需要分别记录这个序列中奇数和偶数的个数，然后输出它们中最小的一个就行了。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int q;
    cin >> q;
    while (q--)
    {
        int n;
        cin >> n;
        int odd = 0, even = 0;
        for (int i = 0; i < n; i++)
        {
            int temp;
            cin >> temp;
            if (temp % 2 == 0)
            {
                even++;
            }
            else
            {
                odd++;
            }
        }
        cout << min(even, odd) << '\n';
    }
}