#P3232. MELON的难题(200分)
-
1000ms
Tried: 71
Accepted: 28
Difficulty: 5
所属公司 :
华为od
MELON的难题(200分)
问题描述
给定一组雨花石的重量,要求将这些石头分成两组,使得两组的重量相等。如果可以实现这样的分组, 输出所需的最小石头数量;如果无法均分,则输出 −1。
解题思路
1. 计算总重量
首先计算所有雨花石的总重量 sum_m。
2. 奇偶性检查
如果 sum_m 为奇数,则无法均分,直接输出 -1。
3. 背包动态规划
设定目标重量为 sum_m / 2。使用动态规划数组 dp,其中 dp[j] 表示形成重量 j 所需的最小石头数量。
- 初始化
dp[0]为0(不需要任何石头形成0重量),其余初始化为一个较大的数(如99,因为n最大只有30)。 - 遍历每个雨花石的重量,并更新
dp数组,以找出形成每个可能重量所需的最少石头数量。
4. 结果输出
最后检查 dp[sum_m / 2]。
- 如果它仍然是初始值,说明无法组成该重量,输出
-1。 - 否则,输出所需的最小石头数量。
5. 时间复杂度
该算法的时间复杂度为 O(n * sum_m / 2),其中 n 是石头的数量,sum_m 是所有石头的总重量。
问题本质分析
本问题实质上是一个变形的“0-1背包问题”。我们需要通过选取雨花石的重量来形成一个特定的目标重量, 这与背包问题中通过物品重量来填充背包的思路类似。通过动态规划的方式,我们可以高效地计算出是否能够达到目标重量, 并在此过程中记录形成该重量所需的最小石头数量。
cpp
#include <bits/stdc++.h>
using namespace std;
void solve() {
int numStones; // 用于存储雨花石的数量
cin >> numStones;
vector<int> stoneWeights(numStones); // 存储每个雨花石的重量
int totalWeight = 0; // 用于存储所有雨花石的总重量
// 输入每个雨花石的重量,并计算总重量
for (int i = 0; i < numStones; i++) {
cin >> stoneWeights[i];
totalWeight += stoneWeights[i]; // 累加当前雨花石重量到总重量
}
// 如果总重量是奇数,则无法均分
if (totalWeight % 2 != 0) {
cout << -1 << endl;
return;
}
// 计算每个人应该得到的目标重量
int targetWeight = totalWeight / 2;
vector<int> minStonesRequired(targetWeight + 1, 99); // DP数组,初始化为99(较大的数)
minStonesRequired[0] = 0; // 表示形成重量0需要0块石头
// 动态规划计算,找出形成目标重量targetWeight所需的最少石头数量
for (int i = 0; i < numStones; i++) { // 遍历每个雨花石
for (int j = targetWeight; j >= stoneWeights[i]; j--) { // 从targetWeight向下遍历
if (j == stoneWeights[i]) // 如果当前重量等于雨花石的重量
minStonesRequired[j] = min(minStonesRequired[j], 1); // 直接赋值为1
else
minStonesRequired[j] = min(minStonesRequired[j], minStonesRequired[j - stoneWeights[i]] + 1); // 更新dp[j]
}
}
// 检查是否能形成目标重量targetWeight
if (minStonesRequired[targetWeight] == 99) // 如果无法形成该重量
cout << -1 << endl;
else
cout << minStonesRequired[targetWeight] << endl; // 输出所需的最小石头数量
}
int main() {
solve();
return 0;
}
python
def solve():
num_stones = int(input()) # 输入雨花石的数量
stone_weights = list(map(int, input().split())) # 输入每个雨花石的重量
total_weight = sum(stone_weights) # 计算所有雨花石的总重量
# 如果总重量是奇数,则无法均分
if total_weight % 2 != 0:
print(-1)
return
# 计算每个人应该得到的目标重量
target_weight = total_weight // 2
min_stones_required = [99] * (target_weight + 1) # DP数组,初始化为99
min_stones_required[0] = 0 # 表示形成重量0需要0块石头
# 动态规划计算,找出形成目标重量target_weight所需的最少石头数量
for weight in stone_weights: # 遍历每个雨花石
for j in range(target_weight, weight - 1, -1): # 从target_weight向下遍历
min_stones_required[j] = min(min_stones_required[j], min_stones_required[j - weight] + 1)
# 检查是否能形成目标重量target_weight
if min_stones_required[target_weight] == 99: # 如果无法形成该重量
print(-1)
else:
print(min_stones_required[target_weight]) # 输出所需的最小石头数量
# 主函数
if __name__ == "__main__":
solve()
java
import java.util.Scanner;
public class Main {
public static void solve() {
Scanner scanner = new Scanner(System.in);
int numStones = scanner.nextInt(); // 输入雨花石的数量
int[] stoneWeights = new int[numStones]; // 存储每个雨花石的重量
int totalWeight = 0; // 用于存储所有雨花石的总重量
// 输入每个雨花石的重量,并计算总重量
for (int i = 0; i < numStones; i++) {
stoneWeights[i] = scanner.nextInt();
totalWeight += stoneWeights[i];
}
// 如果总重量是奇数,则无法均分
if (totalWeight % 2 != 0) {
System.out.println(-1);
scanner.close();
return;
}
// 计算每个人应该得到的目标重量
int targetWeight = totalWeight / 2;
int[] minStonesRequired = new int[targetWeight + 1]; // DP数组
for (int i = 0; i <= targetWeight; i++) {
minStonesRequired[i] = 99; // 初始化为99
}
minStonesRequired[0] = 0; // 表示形成重量0需要0块石头
// 动态规划计算,找出形成目标重量targetWeight所需的最少石头数量
for (int weight : stoneWeights) { // 遍历每个雨花石
for (int j = targetWeight; j >= weight; j--) { // 从targetWeight向下遍历
minStonesRequired[j] = Math.min(minStonesRequired[j], minStonesRequired[j - weight] + 1);
}
}
// 检查是否能形成目标重量targetWeight
if (minStonesRequired[targetWeight] == 99) // 如果无法形成该重量
System.out.println(-1);
else
System.out.println(minStonesRequired[targetWeight]); // 输出所需的最小石头数量
scanner.close();
}
public static void main(String[] args) {
solve();
}
}
题目内容
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 (块数最少)。