当前位置：首页 > java >正文

【华为OD】MVP争夺战（C++、Java、Python）

java 2025/7/13 17:53:43

文章目录

题目描述
- 输入描述
- 输出描述
- 示例
解题思路
- 算法思路
- 核心步骤
代码实现
- C++实现
- Java实现
- Python实现
算法要点
复杂度分析
解题总结

题目描述

在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个人都能拿到MVP，MVP的条件是单场最高分得分获得者。可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，然而比赛过程中的每1分钟的得分都只能由某一个人包揽。

输入描述

第一行为一个数字 t，表示为有得分的分钟数 1 ≤ t ≤ 50
第二行为 t 个数字，代表每一分钟的得分 p，1 ≤ p ≤ 50

输出描述

输出有得分的队员都是MVP时，最少得MVP得分。

示例

输入：

9
5 2 1 5 2 1 5 2 1

输出：

说明：
一共 4 人得分，分别都是 6 分：5 + 1，5 + 1，5 + 1，2 + 2 + 2

解题思路

这是一个数组划分问题，目标是将给定的分数数组分成若干个子集，使得每个子集的和都相等，且子集数量尽可能多（MVP人数最多），这样每个MVP的得分就最小。

算法思路

贪心策略：为了让MVP人数最多，需要让每个MVP的得分尽可能小
枚举验证：从最大可能的MVP人数开始尝试，逐步减少直到找到可行解
回溯分组：使用回溯算法将分数分配到不同的组中，每组代表一个MVP

核心步骤

计算总分，降序排列数组
从最大MVP人数开始枚举
对每个人数，检查总分能否整除
使用回溯算法验证是否能平均分组
返回第一个可行方案的单人得分

代码实现

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;bool canPartition(vector<int>& nums, int target, int k) {int n = nums.size();vector<int> groups(k, 0);function<bool(int)> dfs = [&](int idx) -> bool {if (idx == n) return true;for (int i = 0; i < k; i++) {if (i > 0 && groups[i] == groups[i-1]) continue;if (groups[i] + nums[idx] <= target) {groups[i] += nums[idx];if (dfs(idx + 1)) return true;groups[i] -= nums[idx];}if (groups[i] == 0) break;}return false;};return dfs(0);
}int main() {int n;cin >> n;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}int sum = accumulate(nums.begin(), nums.end(), 0);sort(nums.begin(), nums.end(), greater<int>());for (int target = nums[0]; target <= sum; target++) {if (sum % target == 0) {int k = sum / target;if (canPartition(nums, target, k)) {cout << target << endl;return 0;}}}return 0;
}

Java实现

import java.util.LinkedList;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();LinkedList<Integer> link = new LinkedList<>();for (int i = 0; i < m; i++) {link.add(sc.nextInt());}System.out.println(getResult(link, m));}public static int getResult(LinkedList<Integer> link, int m) {link.sort((a, b) -> b - a);int sum = 0;for (Integer ele : link) {sum += ele;}while (m >= 1) {LinkedList<Integer> linkCopy = new LinkedList<>(link);if (canPartition(linkCopy, sum, m)) return sum / m;m--;}return sum;}public static boolean canPartition(LinkedList<Integer> link, int sum, int m) {if (sum % m != 0) return false;int target = sum / m;if (target < link.get(0)) return false;while (link.size() > 0 && link.get(0) == target) {link.removeFirst();m--;}int[] groups = new int[m];return dfs(link, 0, groups, target);}public static boolean dfs(LinkedList<Integer> link, int index, int[] groups, int target) {if (index == link.size()) return true;int select = link.get(index);for (int i = 0; i < groups.length; i++) {if (i > 0 && groups[i] == groups[i - 1]) continue;if (select + groups[i] <= target) {groups[i] += select;if (dfs(link, index + 1, groups, target)) return true;groups[i] -= select;}}return false;}
}

Python实现

def dfs(arr, groups, index, target):if index == len(arr):return Truefor i in range(len(groups)):if groups[i] + arr[index] <= target:groups[i] += arr[index]if dfs(arr, groups, index + 1, target):return Truegroups[i] -= arr[index]if groups[i] == 0:breakreturn Falsen = int(input())
arr = list(map(int, input().split()))
total_sum = sum(arr)
arr.sort(reverse=True)for target in range(arr[0], total_sum + 1):if total_sum % target == 0:group_count = total_sum // targetgroups = [0] * group_countif dfs(arr, groups, 0, target):print(target)break