MELON的难题- 华为OD统一考试(E卷)

2024华为OD机试（C卷+D卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

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 1 9 8 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(块数最少)。

题解

这道题目是经典的动态规划类型问题。具体来说，它是0/1 背包问题的变形，核心在于判断是否可以将雨花石分成两部分，使得每部分的重量相等，并找到最小的分割块数。

解题思路

1. 问题分析：题目要求将一堆雨花石分为两堆，重量相等。我们可以把问题转换为，能否找到一个子集，使其总重量为所有雨花石总重量的一半。若总重量为奇数，则无法平分，直接返回 -1。
2. 动态规划思路：
   • 定义一个 dp 数组，dp[i] 表示选择若干个雨花石其总重量恰好为 i时最小的选择块数。
   • 初始化时，dp[0] = 0 表示总重量为 0 时需要的雨花石块数为 0，其余 dp[i] 初始化为无穷大。
   • 对每个雨花石，我们更新 dp 数组，尝试是否可以通过当前雨花石的加入，组成目标重量的一部分。
   • 最终通过动态规划判断，是否可以拼出目标重量，并记录最少的块数。
3. 特殊情况：
   • 如果雨花石的总重量为奇数，则无法平分，直接输出 -1。

Java

import java.util.Scanner;
import java.util.Arrays;
/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();  // 读取雨花石数量
        int[] stones = new int[n];  // 保存雨花石的重量
        
        // 输入雨花石的重量并计算总重量
        int total = 0;
        for (int i = 0; i < n; i++) total += stones[i] = sc.nextInt();

        // 总重量为奇数时无法平分
        if (total % 2 == 1) {
            System.out.pr