主人，你好呀~ 今天我们来看一道可爱的题目，Doremy's Paint 3！这道题就像给小猫咪梳毛一样，只要找到规律，就能轻松解决啦，喵~ 让我们一起来看看吧！

题目大意

题目是这样子的喵：Doremy 有一个 n 个正整数的数组 a。她可以随便打乱这个数组的顺序，也就是排列它。我们的任务就是判断，她能不能把这个数组 a 排列成一个‘好’数组呢？

那...什么是‘好’数组呀？一个数组 b 如果是‘好’的，那么它所有相邻元素的和都相等。比如说 b_1+b_2 和 b_2+b_3 的值是一样的，一直到最后 b_{n-1}+b_n，它们都等于同一个数 k。就像 [1, 2, 1]，1+2=3，2+1=3，这就是个‘好’数组啦！

解题思路

要怎么判断能不能排列成‘好’数组呢？我们来挠一挠脑袋，想一想这个‘好’数组有什么特点，喵~

一个‘好’数组 b 满足 b_i + b_{i+1} = k 对所有 i 都成立。

那么，b_1 + b_2 = k，同时 b_2 + b_3 = k。从这两个式子就能看出来，b_1 必须等于 b_3 呀！ 同理，b_2 + b_3 = k，同时 b_3 + b_4 = k，所以 b_2 必须等于 b_4！

这样推下去，我们就会发现，一个‘好’数组的形式一定是 [x, y, x, y, x, ...] 这样交替出现的，对吧？

这说明，排列后的数组里，最多只能有两种不同的数字，我们叫它们 x 和 y 好了。

有了这个发现，问题就简单多啦！我们可以根据原数组 a 中不同数字的种类数量来分类讨论，喵~

情况一：如果数组 a 中有超过两种不同的数字 如果一开始就给了我们三种或更多种不同的数字，比如 [1, 4, 5, 1]。那不管怎么排列，都不可能只剩下两种数字交替出现。所以，这种情况肯定不行，直接输出 'No' 就好啦，喵~

情况二：如果数组 a 中只有一种数字 比如 [10, 10, 10, 10]。所有数字都一样，那怎么排都还是 [10, 10, 10, 10]。相邻元素的和都是 10+10=20，永远相等。这当然是‘好’数组啦！所以这种情况，答案一定是 'Yes'！

情况三：如果数组 a 中正好有两种不同的数字 这是最有趣的一种情况了，喵！假设这两种数字是 x 和 y。我们想把它们排列成 [x, y, x, y, ...] 的形式。

这时候就要看 x 和 y 的数量了。

• 如果数组长度 n 是偶数，比如 n=4，那么排列出来的样子就是 [x, y, x, y]。这需要两个 x 和两个 y。也就是说，x 和 y 的数量必须相等！
• 如果数组长度 n 是奇数，比如 n=5，那么排列出来的样子就是 [x, y, x, y, x] 或者 [y, x, y, x, y]。第一种需要三个 x 和两个 y；第二种需要三个 y 和两个 x。也就是说，两种数字的数量必须刚好差一个！

把这两种子情况合起来看，就是说 x 的数量和 y 的数量之差的绝对值不能超过 1 (abs(count(x) - count(y)) <= 1)。如果满足这个条件，我们就能把它们成功排列，答案就是 'Yes'；否则就是 'No' 啦！

总结一下我们的思路就是：

1. 统计数组 a 中每个数字出现的次数。
2. 看看有多少种不同的数字。
3. 如果种类 > 2，输出 'No'。
4. 如果种类 = 1，输出 'Yes'。
5. 如果种类 = 2，计算这两种数字的个数，如果个数差的绝对值小于等于 1，输出 'Yes'，否则输出 'No'。

是不是很简单呀，喵~

题解代码

下面就是具体的代码实现啦，主人可以参考一下~ 我加了一些注释，方便理解哦。

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <numeric>
#include <algorithm>

void solve() {
    int n;
    std::cin >> n;
    
    // 用一个 map 来统计每个数字出现的次数，喵~
    // map 的 key 是数字本身，value 是它出现的次数
    std::map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        counts[val]++;
    }

    // counts.size() 就是不同数字的种类数量
    // 情况一：种类数大于 2，直接说 No
    if (counts.size() > 2) {
        std::cout << "No\n";
        return;
    }

    // 情况二：种类数等于 1，直接说 Yes
    if (counts.size() == 1) {
        std::cout << "Yes\n";
        return;
    }

    // 能走到这里，说明种类数一定是 2 啦
    // 这是情况三的处理逻辑
    auto it = counts.begin();
    int count1 = it->second; // 第一个数字的个数
    it++;
    int count2 = it->second; // 第二个数字的个数

    // 判断两个数量的差的绝对值是不是小于等于 1
    if (std::abs(count1 - count2) <= 1) {
        std::cout << "Yes\n";
    } else {
        std::cout << "No\n";
    }
}

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

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

    return 0;
}

知识点介绍

这道题虽然简单，但里面也藏着一些有用的知识点呢，喵~

1. std::map / 频次统计：这道题的核心操作就是统计每个数字出现了多少次。std::map 是一个非常方便的工具，它可以建立“键-值”(key-value)的映射关系。在这里，我们用数字本身作为键，用它的出现次数作为值。每次读到一个数字，就把它对应的次数加一。除了 map，用 std::unordered_map 也可以，它通常更快一些，但不会按键排序。对于这道题，排序不重要，所以两者都可以用哦。

2. 构造性问题的分析方法：这道题问的是“能否”构造一个满足条件的数组。这类问题通常的解法不是去真的尝试所有排列（那太慢啦！），而是去分析目标构造（“好”数组）有什么内在的、必须满足的性质。我们通过分析 b_i + b_{i+1} = k 推导出了“最多只有两种数”和“两种数交替出现”这两个关键性质，从而大大简化了问题。这是一种从结果倒推条件的思维方式，非常重要呀！

3. 分类讨论：这是我们解决问题时最常用的武器之一！当一个问题在不同条件下有不同表现时，把它分成几种简单的情况分别处理，会让思路变得非常清晰。就像我们这里，根据不同数字的种类数分成了 1 种、2 种、大于 2 种这三种情况，每种情况的逻辑都很直接，不容易出错，喵~

好啦，这道题的讲解就到这里啦！希望主人能喜欢，喵~ 如果还有其他问题，随时可以再来找我玩哦！