# MELON的难题2026华为OD机试双机位C卷 - 华为OD上机考试双机位C卷华为OD机试双机位C卷真题目录（Java）点击查看: 【全网首发】2026华为OD机位C卷 机考真题题库含考点说明以及在线OJ（Java题解）题目描述MELON有一堆精美的雨花石（数量为n，重量各异），准备送给S和W。MELON希望送给俩人的雨花石重量一致，请你设计一个程序，帮MELON确认是否能将雨花石平均分配。输入描述第1行输入为雨花石个数: n，0 n 31.第2行输入为空格分割的各雨花石重量: m[0] m[1] … m[n - 1]， 0 m[k] 1001不需要考虑异常输入的情况。输出描述如果可以均分，从当前雨花石中最少拿出几块，可以使两堆的重量相等:如果不能均分，则输出-1。用例1输入4 1 1 2 2输出2说明输入第一行代表共4颗雨花石，第二行代表4颗雨花石重量分别为1、1、2、2。均分时只能分别为1,2，需要拿出重量为1和2的两块雨花石，所以输出2。用例2输入10 1 1 1 1 1 9 8 3 7 10输出3说明输入第一行代表共10颗雨花石，第二行代表4颗雨花石重量分别为1、1、1、1、1、9、8、3、7、10 。均分时可以1,1,1,1,1,9,7和10,8,3，也可以1,1,1,1,9.8和10,7,3,1，或者其他均分方式，但第一种只需要拿出重量为10.8,3的3块雨花石，第二种需要拿出4块，所以输出3(块数最少)。解题思路01背包问题的思路：题目要求将雨花石平均分配，即找到一种方法，使得从雨花石中拿出最少的数量，使得两堆雨花石的重量相等。这个问题可以转化为一个01背包问题：从给定的雨花石中选取一些，使得它们的重量之和等于总重量的一半，且选取的雨花石数量最少。01背包问题的核心思路是使用动态规划。具体步骤如下：计算所有雨花石的总重量。如果总重量为奇数，那么无法将雨花石平均分配，直接输出-1。如果总重量为偶数，我们的目标是找到一些雨花石，使得它们的重量之和等于总重量的一半。定义一个动态规划数组dp，其中dp[j]表示从雨花石中选取一些，使得它们的重量之和为j时，所需的最少雨花石数