解题思路

这是一个贪心算法问题。首先需要判断是否可以平分苹果，然后计算最少需要的移动次数。

关键点：

  1. 判断是否可以平分苹果：
    • 总苹果数必须能被奶牛数整除
    • 每次只能移动2个苹果，所以每头奶牛与平均值的差必须是偶数
  2. 计算最少移动次数：
    • 统计高于平均值的奶牛多出的苹果数
    • 每次移动2个苹果，所以需要除以2

算法步骤：

  1. 计算总苹果数和平均值
  2. 检查是否可以平分
  3. 计算需要移动的苹果数
  4. 计算最少移动次数

代码

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(int n, vector<int>& apples) {
        // 计算总苹果数和平均值
        int total = accumulate(apples.begin(), apples.end(), 0);
        if (total % n != 0) {
            return -1;
        }
        
        int avg = total / n;
        int extra = 0;  // 记录需要移动的苹果数
        
        // 检查每头奶牛
        for (int apple : apples) {
            int diff = apple - avg;
            if (diff % 2 != 0) {  // 差值必须是偶数
                return -1;
            }
            if (diff > 0) {  // 统计需要移出的苹果数
                extra += diff;
            }
        }
        
        // 每次移动2个苹果
        return extra / 2;
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<int> apples(n);
    for (int i = 0; i < n; i++) {
        cin >> apples[i];
    }
    
    Solution solution;
    cout << solution.solve(n, apples) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int solve(int n, int[] apples) {
            // 计算总苹果数和平均值
            int total = 0;
            for (int apple : apples) {
                total += apple;
            }
            
            if (total % n != 0) {
                return -1;
            }
            
            int avg = total / n;
            int extra = 0;  // 记录需要移动的苹果数
            
            // 检查每头奶牛
            for (int apple : apples) {
                int diff = apple - avg;
                if (diff % 2 != 0) {  // 差值必须是偶数
                    return -1;
                }
                if (diff > 0) {  // 统计需要移出的苹果数
                    extra += diff;
                }
            }
            
            // 每次移动2个苹果
            return extra / 2;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] apples = new int[n];
        for (int i = 0; i < n; i++) {
            apples[i] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.solve(n, apples));
        
        sc.close();
    }
}

class Solution:
    def solve(self, n: int, apples: list) -> int:
        # 计算总苹果数和平均值
        total = sum(apples)
        if total % n != 0:
            return -1
        
        avg = total // n
        moves = 0
        extra = 0  # 记录需要移动的苹果数
        
        # 检查每头奶牛
        for apple in apples:
            diff = apple - avg
            if diff % 2 != 0:  # 差值必须是偶数
                return -1
            if diff > 0:  # 统计需要移出的苹果数
                extra += diff
        
        # 每次移动2个苹果
        return extra // 2

# 读取输入
n = int(input())
apples = list(map(int, input().split()))

solution = Solution()
print(solution.solve(n, apples))

算法及复杂度

时间复杂度

  • 计算总和和检查每头奶牛：
  • 总时间复杂度：

空间复杂度

  • 只需要常数额外空间：

正确性证明

  1. 如果总苹果数不能被奶牛数整除，显然无解
  2. 如果某头奶牛与平均值的差不是偶数，由于每次只能移动2个苹果，也无解
  3. 统计所有高于平均值的奶牛多出的苹果数，除以2即为最少移动次数
    • 因为每次移动2个苹果
    • 多出的苹果必须移动到缺少苹果的奶牛那里
    • 由于总数平衡，多出的苹果数等于缺少的苹果数