【分糖果】题解

题干信息解读
问题描述：有n个小朋友，每个小朋友持有若干糖果。老师每次可从一个小朋友手中取走 2 颗糖果并分给另一个小朋友，求最少操作次数使所有小朋友糖果数相同；若无法实现则输出 - 1。
核心约束：
1.每次操作必须移动 2 颗糖果（不可拆分）。
2.总糖果数必须能被n整除，否则无法均分。
3.每个小朋友的糖果数与平均值的差值必须为偶数，否则无法通过每次移动 2 颗完成调整。

整体做题思路
可行性判断：
1.计算总糖果数 totalCandies，若无法被n整除，直接返回 - 1。
2.计算目标平均值 targetCandy = totalCandies / n 。
差值检查与操作次数计算：
1.遍历每个小朋友的糖果数，计算其与目标值的差值difference。
2.若 difference 为奇数，说明无法通过每次移动 2 颗糖果实现平衡，返回 - 1。
3.仅累加 difference > 0 的情况，总操作次数为所有正数差值之和除以 2。
数学原理：
1.当总和能被n整除时，所有多出的糖果数之和等于所有缺少的糖果数之和的绝对值。因此，仅需计算需要送出糖果的次数即可。
2.每次操作可同时解决一个送出和一个接收的需求，因此总操作次数为总多余糖果数 / 2。

难点和注意事项
差值奇偶性检查：
每个小朋友的糖果数与平均值的差值必须为偶数，否则无法通过每次移动 2 颗糖果实现平衡。这是本题的关键约束。
避免冗余计算：
只需统计正数差值之和，无需处理负数部分，因为总和平衡时正数部分总和等于负数部分绝对值之和。
边界条件：
1.当n=1时，直接返回 0（无需操作）。
2.当所有小朋友糖果数相同时，操作次数为 0。

AC代码（如有雷同，纯属巧合）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int childCount;
    cin >> childCount;
    
    vector<int> candyCounts(childCount);
    int totalCandies = 0;
    
    // 输入每个小朋友的糖果数并计算总和
    for (int i = 0; i < childCount; ++i) {
        cin >> candyCounts[i];
        totalCandies += candyCounts[i];
    }
    
    // 判断是否能平均分配
    if (totalCandies % childCount != 0) {
        cout << -1 << endl;
        return 0;
    }
    
    int targetCandy = totalCandies / childCount;
    int difference = 0;
    int operationCount = 0;
    
    // 计算需要的总操作次数
    for (int i = 0; i < childCount; ++i) {
        difference = candyCounts[i] - targetCandy;
        
        // 若差值为奇数，无法通过每次移动2颗糖果实现，输出-1
        if (difference % 2 != 0) {
            cout << -1 << endl;
            return 0;
        }
        
        // 只累加需要送出糖果的情况
        if (difference > 0) {
            operationCount += difference / 2;
        }
    }
    
    cout << operationCount << endl;
    return 0;
}

复杂度分析
时间复杂度：O(n)
仅需遍历一次数组计算总和和差值。
空间复杂度：O(n)
存储每个小朋友的糖果数。
该算法在数据规模 n ≤ 100000 下高效可行，满足题目要求。