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

输出：

说明：
输入表示 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;
}