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

文章目录

题目描述
解题思路
- 算法思路
- 核心步骤
代码实现
算法要点
复杂度分析
解题总结

题目描述

在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个人都能拿到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 True
    
    for i in range(len(groups)):
        if groups[i] + arr[index] <= target:
            groups[i] += arr[index]
            if dfs(arr, groups, index + 1, target):
                return True
            groups[i] -= arr[index]
        
        if groups[i] == 0:
            break
    
    return False

n = 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 // target
        groups = [0] * group_count
        if dfs(arr, groups, 0, target):
            print(target)
            break

算法要点

核心思想：

将数组分成k个和相等的子集，使k尽可能大
使用回溯算法将元素分配到不同组中
从最优解开始搜索，找到第一个可行解

剪枝优化：

相同组剪枝：相同容量的组只尝试第一个
空组剪枝：如果空组放不下，跳过后续空组
预处理：先处理等于目标值的元素
排序优化：大元素优先处理，便于剪枝

复杂度分析

时间复杂度：O(k^n)，k为组数，n为元素个数
空间复杂度：O(k)，用于存储各组当前和

解题总结

MVP争夺战本质上是数组划分问题，通过贪心策略确定搜索方向，回溯算法验证可行性，结合多种剪枝技巧提高效率。关键是理解问题的数学本质：寻找最大的k值，使得数组能被分成k个和相等的子集。

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