【华为OD-E卷-MVP争夺战 100分（python、java、c++、js、c）】
【华为OD-E卷-MVP争夺战 100分（python、java、c++、js、c）】
题目
在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个人都能拿到MVP，MVP的条件是单场最高分得分获得者。
可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，
然而比赛过程中的每1分钟的得分都只能由某一个人包揽
输入描述
- 输入第一行为一个数字 t ，表示为有得分的分钟数
1 ≤ t ≤ 50 第二行为 t 个数字，代表每一分钟的得分 p，
1 ≤ p ≤ 50
输出描述
- 输出有得分的队员都是MVP时，最少得MVP得分
用例
用例一：
输入：
9
5 2 1 5 2 1 5 2 1
输出：
6
python解法
- 解题思路：
- 本问题的目标是将球员的得分分成若干队伍（最多 t 个队伍），并使得每个队伍的得分尽可能接近。最终返回的是每个队伍的最大可能得分。
具体思路：
计算总得分：
首先计算所有球员的总得分。
最大分配值的二分查找：
假设每个队伍可以获得的最大得分为 total // count。
检查是否能够将球员分配到 count 个队伍，使每队得分恰好为 total // count。
分组问题的递归回溯：
通过回溯算法尝试将球员分配到 count 个队伍中。
每个队伍的得分不超过目标值 goal。
若所有球员成功分配，返回 True；否则，尝试减少队伍数量并重新分配。
关键点：
利用递归回溯解决分组问题。
通过逐步减少队伍数量，找到最优的最大得分分配方案。
class TeamMVP:
def __init__(self, points):
# 初始化球员得分列表
self.points = points
def calc_mvp(self, count):
# 计算总得分
total = sum(self.points)
# 从最多 count 个队伍开始尝试，逐步减少队伍数量
while count > 0:
# 检查是否可以分成 count 个队伍，目标每队得分为 total // count
if self.divide_teams(total // count, count):
return total // count
count -= 1
# 如果无法分组，返回总得分
return total
def divide_teams(self, goal, players):
# 检查是否可以分成 players 个队伍且每队得分为 goal
if sum(self.points) % players != 0 or goal < max(self.points):
return False
# 初始化每个队伍的当前得分
buckets = [0] * players
# 将球员得分从高到低排序
self.points.sort(reverse=True)
def backtrack(idx):
# 如果所有球员都成功分配，返回 True
if idx == len(self.points):
return True
for j in range(players):
# 跳过重复的队伍分配，避免重复计算
if j > 0 and buckets[j] == buckets[j - 1]:
continue
# 如果当前球员可以加入队伍 j 且不超过目标值
if buckets[j] + self.points[idx] <= goal:
buckets[j] += self.points[idx] # 加入队伍 j
# 递归分配下一个球员
if backtrack(idx + 1):
return True
buckets[j] -= self.points[idx] # 回溯，移除当前球员
return False
return backtrack(0)
if __name__ == "__main__":
# 输入队伍数量和球员得分
t = int(input())
scores = list(map(int, input().split()))
# 创建 MVP 计算器对象
mvp_calculator = TeamMVP(scores)
# 输出每队最大可能得分
print(mvp_calculator.calc_mvp(t))
java解法
- 解题思路
- 本问题的目标是将分数 scores 分成最多 t 个队伍，并使得每个队伍的得分尽可能相等。要求输出每队的最大可能得分。
具体思路：
总分计算与排序：
首先计算总分 total 并对分数从高到低排序，方便在回溯时优先分配高分。
逐步尝试减少队伍数：
从最多 t 个队伍开始尝试，将总分均分到 t 个队伍中。
如果不能满足，减少队伍数 t 并重新尝试。
检查分配可能性：
目标分数为 total / t，每队必须恰好达到目标分数。
检查是否可以通过回溯算法将分数分配到 t 个队伍中，使每队总分为 targetScore。
回溯分配：
使用递归回溯分配分数，尝试将每个分数放入某个队伍中。
剪枝优化：
如果当前分数无法放入队伍（超过目标值），则跳过。
如果两个队伍当前得分相同，则跳过重复尝试。
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// 读取输入：队伍数量和分数
int t = input.nextInt();
ArrayList<Integer> scores = new ArrayList<>();
for (int i = 0; i < t; i++) {
scores.add(input.nextInt());
}
// 计算并输出每队的最大可能得分
System.out.println(calculateMVPScore(scores, t));
}
// 计算每队最大可能的得分
public static int calculateMVPScore(ArrayList<Integer> scores, int t) {
// 对分数降序排序
Collections.sort(scores, Collections.reverseOrder());
// 计算总得分
int total = scores.stream().mapToInt(Integer::intValue).sum();
// 从最多 t 个队伍开始尝试，逐步减少队伍数量
while (t >= 1) {
// 创建分数副本以避免修改原数据
ArrayList<Integer> scoresCopy = new ArrayList<>(scores);
// 检查是否可以分配
if (canDistributeScores(scoresCopy, total, t)) {
return total / t;
}
t--; // 减少队伍数量
}
// 如果无法分组，返回总分
return total;
}
// 检查是否可以将分数分配到 teams 个队伍中
private static boolean canDistributeScores(ArrayList<Integer> scores, int total, int teams) {
// 如果总分不能被整除或目标分数小于最大分数，直接返回 false
if (total % teams != 0) return false;
int targetScore = total / teams;
if (targetScore < scores.get(0)) return false;
// 如果某些分数直接等于目标值，优先分配到队伍中
while (!scores.isEmpty() && scores.get(0) == targetScore) {
scores.remove(0);
teams--;
}
// 初始化队伍得分数组
int[] buckets = new int[teams];
// 使用回溯分配分数
return distribute(scores, 0, buckets, targetScore);
}
// 回溯分配分数到队伍
private static boolean distribute(ArrayList<Integer> scores, int index, int[] buckets, int target) {
// 如果所有分数都已分配，返回 true
if (index == scores.size()) return true;
int currentScore = scores.get(index);
// 尝试将当前分数分配到每个队伍
for (int i = 0; i < buckets.length; i++) {
// 跳过重复的队伍分配（优化剪枝）
if (i > 0 && buckets[i] == buckets[i - 1]) continue;
// 如果当前分数可以加入队伍
if (buckets[i] + currentScore <= target) {
buckets[i] += currentScore;
// 递归分配下一个分数
if (distribute(scores, index + 1, buckets, target)) return true;
// 回溯，移除当前分数
buckets[i] -= currentScore;
}
}
return false;
}
}
C++解法
- 解题思路
更新中
C解法
更新中
JS解法
具体思路：
计算总分：
首先计算所有分数的总和 sum。
从最多 mins 个队伍开始尝试，逐步减少队伍数量，直到找到最大可能分数。
检查分配是否可行：
如果 sum 不能被当前队伍数量整除，跳过。
如果可以整除，目标分数为 sum / p，尝试分配分数。
递归回溯分配：
使用回溯算法尝试将分数分配到每个队伍。
剪枝优化：
跳过重复的分配方案。
如果当前队伍的分数加上当前分数大于目标分数，则直接跳过
const readline = require('readline');
// 主函数：处理输入并调用逻辑
function main() {
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let t; // 用于存储队伍的数量
rl.on('line', (line) => {
if (!t) {
// 读取第一行输入，队伍数量
t = parseInt(line);
} else {
// 读取第二行输入，分数列表
const pts = line.split(' ').map(Number);
const res = calcMVP(t, pts);
console.log(res);
rl.close();
}
});
}
// 计算 MVP 分数的函数
function calcMVP(mins, pts) {
// 计算总分
const sum = pts.reduce((a, b) => a + b, 0);
// 尝试从最多队伍数量逐步减少
for (let p = mins; p >= 1; p--) {
// 检查是否可以将分数均分为 p 个队伍
if (sum % p === 0 && valid(p, sum / p, [...pts])) {
return sum / p; // 如果可以分配，返回每个队伍的分数
}
}
return sum; // 如果无法分配，返回总分
}
// 检查是否能合理分配分数
function valid(pl, tgt, pts) {
// 按分数从大到小排序，方便优先分配高分
pts.sort((a, b) => b - a);
// 如果最高分大于目标分数，直接返回 false
if (pts[0] > tgt) return false;
// 初始化每个队伍的当前得分
const alloc = new Array(pl).fill(0);
// 使用回溯算法检查是否可以分配
return dfs(0, pts, tgt, alloc);
}
// 递归分配函数
function dfs(idx, pts, tgt, alloc) {
// 如果所有分数都已成功分配，返回 true
if (idx === pts.length) return true;
// 获取当前分数
const current = pts[idx];
// 尝试将当前分数分配到每个队伍
for (let i = 0; i < alloc.length; i++) {
// 跳过重复的队伍分配方案
if (i > 0 && alloc[i] === alloc[i - 1]) continue;
// 如果当前队伍可以接受当前分数
if (alloc[i] + current <= tgt) {
alloc[i] += current; // 将分数分配给队伍
// 递归分配下一个分数
if (dfs(idx + 1, pts, tgt, alloc)) return true;
alloc[i] -= current; // 回溯，移除当前分数
}
}
return false; // 如果无法分配，返回 false
}
// 启动主函数
main();
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏