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

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

华为od机试

题目描述

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

输出：

说明：输入表示 4 块雨花石，第二行代表4颗雨花石的重量分别为 1，1，2，2。均分时只能分别为1,2，需要拿出重量为1和2的两块雨花石，所以输出2。

示例2

输入：

10
1 1 1 1 1 1 9 8 7 10

输出：

说明：输入第一行代表共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。

动态规划思路：

定义一个 dp 数组，dp[i] 表示选择若干个雨花石其总重量恰好为 i时最小的选择块数。

初始化时，dp[0] = 0 表示总重量为 0 时需要的雨花石块数为 0，其余 dp[i] 初始化为无穷大。

对每个雨花石，我们更新 dp 数组，尝试是否可以通过当前雨花石的加入，组成目标重量的一部分。

最终通过动态规划判断，是否可以拼出目标重量，并记录最少的块数。

特殊情况：

如果雨花石的总重量为奇数，则无法平分，直接输出 -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.println(-1);
            return;
        }

        // 目标是找到总重量为一半的子集
        int half = total / 2;

        // dp[x] 表示分配总重量 x 时拿出最少的块数
        int[] dp = new int[half + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);  // 初始化 dp 数组为最大值
        dp[0] = 0;  // 重量为 0 时需要的雨花石数为 0

        // 动态规划更新 dp 数组
        for (int stone : stones) {
            for (int j = half; j >= stone; j--) {
                if (dp[j - stone] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - stone] + 1);
                }
            }
        }

        // 输出结果，判断是否可以找到重量为 half 的子集
        System.out.println(dp[half] == Integer.MAX_VALUE ? -1 : dp[half]);
    }
}

Python

def solve(stones):
    total = sum(stones)

    # 如果总重量是奇数，无法平分
    if total % 2:
        return -1

    # 目标是找到总重量为一半的子集
    half = total // 2

    # dp[x] 表示分配总重量 x 时拿出最少的块数
    dp = [float('inf')] * (half + 1)
    dp[0] = 0

    # 动态规划，更新 dp 数组
    for stone in stones:
        for j in range(half, stone - 1, -1):
            if dp[j - stone] != float('inf'):
                dp[j] = min(dp[j], dp[j - stone] + 1)

    # 输出结果
    return -1 if dp[half] == float('inf') else dp[half]


if __name__ == '__main__':
    n = int(input())  # 读取雨花石数量
    stones = list(map(int, input().split()))  # 输入雨花石的重量

    # 输出结果
    print(solve(stones))

C++

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

int main()
{
    int n;
    cin >> n;
    vector<int> stones(n);
    int         tot = 0;
    for (int i = 0; i < n; i++) {
        cin >> stones[i];
        tot += stones[i];
    }

    // 总重量为奇数不可能平分
    if (tot % 2) {
        cout << -1 << endl;
        return 0;
    }

    // 目标是找到总重量为一半的子集
    int half = tot / 2;
    //  dp[x] 表示分配总重量 x 时拿出最少的块数
    vector<int> dp(half + 1, INT_MAX);
    dp[0] = 0;

    for (int stone : stones) {
        for (int j = half; j >= stone; j--) {
            if (dp[j - stone] != INT_MAX) {
                dp[j] = min(dp[j], dp[j - stone] + 1);
            }
        }
    }

    cout << (dp[half] == INT_MAX ? -1 : dp[half]) << endl;

    return 0;
}