哈喵~ 各位同学，今天我们来看一道非常“时髦”的题目，A. Fashionable Array！听起来就很有趣对不对？让本喵带大家一起来看看怎么解决它吧！ nya~ (^・ω・^§)ﾉ

题目大意

这道题是说，在遥远的 2077 年，连数组都开始追求时尚了喵！一个数组被称为“时髦的”，当且仅当它里面最小值和最大值的和能被 2 整除。

举个栗子：数组 [3, 1, 5, 9]，最小值是 1，最大值是 9。它们的和是 1 + 9 = 10，10 可以被 2 整除，所以这个数组就是“时髦的”~

现在给你一个数组 a，你可以通过“移除元素”这个操作来修改它。题目问你，最少需要移除多少个元素，才能让剩下的数组变得“时髦”呢？

题解方法

哼哼，想让本喵动脑筋？没问题！让我想想... (ฅ'ω'ฅ)

首先，我们要弄清楚“最小值和最大值的和能被 2 整除”到底是什么意思。 两个数的和是偶数，只有两种情况：

1. 偶数 + 偶数 = 偶数
2. 奇数 + 奇数 = 偶数

也就是说，一个数组是“时髦的”，等价于它的最小值和最大值有相同的奇偶性（要么都是奇数，要么都是偶数）。这是解题的关键哦！

我们的目标是最小化移除的元素数量。反过来想，这不就是最大化保留的元素数量嘛！

那么，我们最终保留下来的那个“时髦”数组，它的最小值和最大值肯定是从原始数组里选出来的元素，对吧？

所以，一个很自然的想法就出现啦：我们可以枚举原始数组中的任意两个元素 a[i] 和 a[j]，把它们当作我们最终数组的候选最小值和最大值。

假设我们选定了 min_val = min(a[i], a[j]) 和 max_val = max(a[i], a[j])。

1. 检查合法性：首先，min_val 和 max_val 必须满足“时髦”条件，也就是它们的奇偶性要相同。如果一个奇一个偶，那它们就不可能成为同一个时髦数组的最小和最大值，直接跳过这对组合，寻找下一对，喵~

2. 计算移除数：如果 min_val 和 max_val 奇偶性相同，那么它们就是一组合法的候选。为了让它们成为最终的最小值和最大值，我们必须保留所有在 [min_val, max_val] 区间内的原始数组元素，并移除所有小于 min_val 或大于 max_val 的元素。 所以，对于这一对候选，需要移除的元素数量就是原始数组里所有 < min_val 或 > max_val 的元素的总数。

3. 找到最优解：我们遍历所有可能的 (a[i], a[j]) 组合，计算每种合法情况下需要移除的元素数量，然后取一个最小值，就是我们的答案啦！

为了快速计算“需要移除的元素数量”，我们可以先把原始数组排个序。在一个排好序的数组里，要找有多少个元素小于 x 或者大于 y，用二分查找（C++ 里的 lower_bound 和 upper_bound）就会非常快！

哦，对了，还有一个最坏的情况：我们可以移除 n-1 个元素，只留下一个。这时候最小值和最大值是同一个数，它们的和肯定是偶数，所以这永远是一个合法的“时髦”数组。所以我们的答案最多是 n-1。

总结一下本喵的思路：

1. 对数组 a 进行排序，得到 sorted_a。
2. 初始化最小移除次数 min_removals = n - 1。
3. 用两层循环遍历 a 中所有的元素对 (a[i], a[j])，作为候选的 min_val 和 max_val。
4. 检查 min_val 和 max_val 的奇偶性，如果不同则跳过。
5. 如果奇偶性相同，就在排好序的 sorted_a 中，用二分查找计算出小于 min_val 和大于 max_val 的元素总数 current_removals。
6. 更新 min_removals = min(min_removals, current_removals)。
7. 所有组合都试过之后，min_removals 就是最终答案啦！

题解 (C++)

这是本喵写好的代码，加了些注释，方便大家理解哦~

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 如果数组只有一个或零个元素，它已经是时髦的了，不需要操作，喵~
    if (n <= 1) {
        std::cout << 0 << std::endl;
        return;
    }

    // 最坏的情况是移除 n-1 个元素，只留一个。
    int min_removals = n - 1;

    // 创建一个排好序的数组副本，方便后面快速统计元素个数。
    std::vector<int> sorted_a = a;
    std::sort(sorted_a.begin(), sorted_a.end());

    // 暴力枚举所有可能的最小值和最大值组合。
    // 最终时髦数组的 min 和 max 一定是原数组中存在的元素。
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int min_val = std::min(a[i], a[j]);
            int max_val = std::max(a[i], a[j]);

            // 检查奇偶性是否相同，这是“时髦”的充要条件喵~
            if ((min_val % 2) != (max_val % 2)) {
                continue; // 奇偶性不同，这对组合不行，换下一对！
            }

            // 如果选定了 min_val 和 max_val，就需要移除所有不在 [min_val, max_val] 区间内的元素。
            // 我们在排好序的数组上用二分查找来高效地计数。

            // 找到第一个不小于 min_val 的元素的位置。
            auto it_low = std::lower_bound(sorted_a.begin(), sorted_a.end(), min_val);
            // 找到第一个大于 max_val 的元素的位置。
            auto it_high = std::upper_bound(sorted_a.begin(), sorted_a.end(), max_val);

            // 计算需要移除的元素数量
            // 小于 min_val 的元素数量
            int removals_below = std::distance(sorted_a.begin(), it_low);
            // 大于 max_val 的元素数量
            int removals_above = std::distance(it_high, sorted_a.end());
            
            int current_removals = removals_below + removals_above;
            min_removals = std::min(min_removals, current_removals);
        }
    }

    std::cout << min_removals << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然不难，但里面藏着一些很有用的小知识点哦，本喵来给大家梳理一下！

1. 奇偶性 (Parity) 这是本题的核心数学概念。两个整数的和是偶数，当且仅当这两个整数的奇偶性相同。

   • 偶 + 偶 = 偶 (e.g., 2 + 4 = 6)
   • 奇 + 奇 = 偶 (e.g., 3 + 5 = 8)
   • 奇 + 偶 = 奇 (e.g., 3 + 4 = 7) 所以题目中的 (min(a) + max(a)) % 2 == 0 可以直接转化为 min(a) % 2 == max(a) % 2。这个转换让问题清晰多了！

2. 暴力枚举 (Brute-force Enumeration) 我们的解法中，通过两层循环尝试了所有可能的 (a[i], a[j]) 组合作为最终的最小/最大值。这种“把所有可能性都试一遍”的朴素思想就是暴力枚举。因为本题的 n 最大只有 50，n*n 的复杂度完全可以接受，所以暴力枚举是一个非常直接有效的策略。

3. 二分查找：std::lower_bound 和 std::upper_bound 就像猫猫在书架上找罐头一样，二分查找能帮你很快地找到想要的东西喵！这两个是 C++ STL 中非常有用的函数，必须在有序的序列上使用。

   • std::lower_bound(begin, end, val): 在 [begin, end) 范围内查找，返回第一个不小于 val 的元素的位置（迭代器）。也就是 x >= val 的第一个 x。
   • std::upper_bound(begin, end, val): 在 [begin, end) 范围内查找，返回第一个大于 val 的元素的位置（迭代器）。也就是 x > val 的第一个 x。

   在我们的代码里：

   • std::distance(sorted_a.begin(), it_low) 计算了从数组开头到第一个 >= min_val 的元素之间的距离，这恰好就是所有 < min_val 的元素的数量。
   • std::distance(it_high, sorted_a.end()) 计算了从第一个 > max_val 的元素到数组结尾的距离，这恰好就是所有 > max_val 的元素的数量。

   通过这两个函数，我们可以在 O(log n) 的时间内完成计数，比一个个地去数要快得多！

好啦，今天的题解就到这里啦！希望大家都能明白。如果还有问题，可以随时再来找本喵哦！拜拜~ 喵呜~ (づ｡◕‿‿◕｡)づ