哈喽，主人！今天我们来看一道超级可爱的题目 B. Fair Division 喵~ 别看它简单，里面可藏着一些非常重要的小知识点哦。就让本猫娘来带你一步步解开它吧！(ฅ´ω`ฅ)

题目大意

主人，这个问题是这样的喵~

Alice 和 Bob 有一堆糖果，这些糖果只有两种重量：1克和2克。他们想把所有糖果分给两个人，目标是让 Alice 手里的糖果总重量和 Bob 手里的一模一样。

我们需要判断一下，他们到底能不能实现这个“公平分配”的愿望呢？

举个例子：

• 如果有两颗1克的糖果，那一人一个，重量都是1，可以！(YES)
• 如果有一颗1克和一颗2克的糖果，总重是3，怎么分都不可能一样重，不行！(NO)
• 如果有两颗1克和两颗2克的糖果，可以一人拿一颗1克和一颗2克，两个人的重量都是3，可以！(YES)

题解方法

要让两个人分到的糖果重量相等，一个最最基本的前提就是：所有糖果的总重量必须是个偶数！如果总重量是奇数，比如3克，那怎么分也不可能分成两个相等的整数呀，对不对？糖果又不能切开~

所以，我们的第一步就是算出所有糖果的总重量 total_sum。

• 如果 total_sum 是奇数，那肯定分不了，直接告诉他们 "NO" 就好啦。
• 如果 total_sum 是偶数，那么理论上是可以平分的。每个人应该分到 half_sum = total_sum / 2 的重量。

现在问题就变成了：我们能不能用手里的1克和2克糖果，凑出 half_sum 这么重的糖果堆给其中一个人呢？（只要一个人凑够了，剩下的自然就是另一半啦）

这里就要再分两种情况讨论啦，喵~

情况一：half_sum 是偶数

如果目标重量 half_sum 是个偶数，那事情就简单多啦！ 我们可以优先用2克的糖果去凑，因为2克糖果本身就是偶数，不管用多少个，凑出来的重量也都是偶数。如果2克糖果不够，剩下的重量也一定是偶数，这时候就可以用1克的糖果（两个两个地用）来补齐。 因为 total_sum = (1克糖果数) + 2 * (2克糖果数) 是偶数，而 2 * (2克糖果数) 本身就是偶数，所以 1克糖果数 必须是偶数。 既然 half_sum 是偶数，而且我们有偶数个1克糖果，就总能凑出来！所以只要 half_sum 是偶数，就一定可以，直接回答 "YES"！

情况二：half_sum 是奇数

如果目标重量 half_sum 是个奇数，那事情就稍微有点不一样了。 只用2克的糖果是凑不出奇数的，对吧？所以，我们必须，必须，必须（重要的事情说三遍喵！）用上至少一个1克的糖果。 只要我们手里有1克的糖果（也就是1克糖果的数量 count1 > 0），我们就可以先拿一个1克的糖果，剩下的目标重量 half_sum - 1 就变成偶数啦，然后就回到了情况一的简单模式，可以用2克糖果和成对的1克糖果去凑。 所以，只要 half_sum 是奇数，并且我们有至少一个1克糖果，就能凑出来，回答 "YES"！

那要是我们一个1克的糖果都没有 (count1 == 0)，那就没办法凑出奇数重量了，只能遗憾地说 "NO" 啦~ (´;ω;`)

总结一下思路就是：

1. 统计1克和2克糖果的数量，算出总重量。
2. 如果总重量是奇数 -> NO。
3. 如果总重量是偶数，算出一半的重量 half_sum。
4. 如果 half_sum 是偶数 -> YES。
5. 如果 half_sum 是奇数，看看有没有1克糖果。
   • 有 (count1 > 0) -> YES。
   • 没有 (count1 == 0) -> NO。

题解代码

这是本猫娘为主人的实现准备的 C++ 代码，加上了详细的注释哦~

#include <iostream>

// Meow~ 这是解决单个测试用例的函数哦
void solve() {
    int n;
    std::cin >> n; // 读取糖果的数量
    int count1 = 0; // 记录1克糖果的数量
    int count2 = 0; // 记录2克糖果的数量
    for (int i = 0; i < n; ++i) {
        int weight;
        std::cin >> weight;
        if (weight == 1) {
            count1++;
        } else {
            // weight is 2
            count2++;
        }
    }

    // 计算所有糖果的总重量，喵~
    long long total_sum = (long long)count1 * 1 + (long long)count2 * 2;

    // 如果总重量是奇数，那肯定没法平分啦
    if (total_sum % 2 != 0) {
        std::cout << "NO\n";
        return;
    }

    // 如果总重量是偶数，每个人应该分到一半
    long long half_sum = total_sum / 2;

    // 如果每个人要分的重量 half_sum 是偶数
    // 这种情况总是可以实现的，喵~
    // 我们可以用一些2克糖果和偶数个1克糖果来凑
    if (half_sum % 2 == 0) {
        std::cout << "YES\n";
    } else {
        // 如果 half_sum 是奇数，我们必须用奇数个1克糖果来凑
        // 这就要求我们至少得有1个1克糖果才行
        if (count1 > 0) {
            std::cout << "YES\n";
        } else {
            // 如果一个1克糖果都没有，那就没办法凑出奇数重量了 (´;ω;`)
            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. 奇偶性分析 (Parity Analysis)

这道题的核心就是 奇偶性！奇偶性是数字的一个基本属性，一个整数要么是奇数，要么是偶数。

• 偶数 + 偶数 = 偶数
• 奇数 + 奇数 = 偶数
• 偶数 + 奇数 = 奇数

在题目里，总重量必须是偶数才能平分，这是因为平分就是 总重量 / 2，如果总重量是奇数，除以2就会有余数，但糖果不能切开呀！

同样的，当我们考虑如何凑出目标重量 half_sum 时，也用到了奇偶性。要凑出奇数，必须使用奇数个1（奇数）。要凑出偶数，可以用任意个2（偶数）和偶数个1（偶数）。

奇偶性分析在很多算法问题里都是一个超级好用的快速判断工具哦，喵~

2. 分类讨论 (Casework)

我们的解法里，先判断总重量的奇偶，再判断 half_sum 的奇偶，这就是 分类讨论 的思想。

当一个问题看起来有点复杂时，可以根据某些关键条件（比如这里的奇偶性），把它分解成几个更简单、更容易处理的子问题。每个子问题都解决了，整个问题也就解决啦！这就像猫猫先把毛线球拆开，再一根一根地理顺一样，喵~

学会把大问题拆成小问题，是成为编程高手的必经之路哦，主人加油！(๑•̀ㅂ•́)و✧