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

华为OD机试 - 星际篮球争霸赛 - 回溯（Java 2024 E卷 200分）

news 2025/5/9 7:26:03

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个队员都能拿到 MVP。MVP的条件是单场最高得分得分者。

可以安排队列让宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，然而比赛过程中的每1分钟的得分都只能由某一个人包揽。

二、输入描述

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

三、输出描述

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

四、测试用例

测试用例1：

1、输入

9
5 2 1 5 2 1 5 2 1

2、输出

3、说明

一共 4 人得分，分别都是 6 分。5+1，5+1，5+1，2+2+2

测试用例2：

1、输入

5
3 3 3 3 3

2、输出

3、说明

每个队员得分为3，共5个队员。

五、解题思路

1、问题分析

需要将每一分钟的得分分配给尽可能多的队员，使得所有队员的总得分相同，并且每个队员的得分都是MVP（即得分最高的队员）。换句话说，我们需要将所有得分分配给若干队员，使得每个队员的总得分相同，且这个总得分尽可能小。

2、排序优化

首先将得分数组按降序排序，这样可以优先分配较大的得分，减少回溯的深度，提高效率。

3、剪枝策略

如果当前得分大于目标得分 target，则直接跳过该 k。

在回溯过程中，如果某个队员已经尝试过某个得分但未成功，则跳过相同的情况，避免重复计算。

如果某个队员的得分为0，且当前得分无法分配给他，则后续队员也无法分配该得分，直接终止该分支。

4、具体步骤

计算总得分：首先计算所有得分的总和 sum。
尝试不同的队员数量：从最大的可能队员数量（即 t）开始，逐步减少，直到找到一个能够将总得分均匀分配给这些队员的数量 k。
验证可行性：
- 检查 sum 是否能被 k 整除。如果不能，继续尝试下一个 k。
- 如果可以，计算每个队员的目标得分 S = sum / k。
- 使用回溯法尝试将所有得分分配给 k 个队员，使得每个队员的总得分恰好为 S。
确定最小的 MVP 得分：一旦找到满足条件的 k，对应的 S 就是所求的最小 MVP 得分。

六、Java算法源码

public class OdTest {private static int[] scores; // 存储每一分钟的得分private static int n; // 得分的分钟数private static int totalSum; // 所有得分的总和public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt(); // 读取得分的分钟数scores = new int[n];for(int i = 0; i < n; i++) {scores[i] = sc.nextInt(); // 读取每一分钟的得分totalSum += scores[i]; // 计算总得分}// 对得分进行降序排序，便于优化回溯过程Arrays.sort(scores);for(int i =0; i < n/2; i++) {int temp = scores[i];scores[i] = scores[n-1-i];scores[n-1-i] = temp;}// 从最大可能的队员数量开始尝试for(int k = n; k >=1; k--) {if(totalSum % k != 0) continue; // 如果总得分不能被k整除，则跳过int target = totalSum / k; // 每个队员的目标得分// 如果最大的单个得分大于目标得分，则不可能分配if(scores[0] > target) continue;// 初始化每个队员当前的得分int[] buckets = new int[k];// 尝试将得分分配到各个队员if(canPartition(0, buckets, target)) {System.out.println(target); // 输出最小的 MVP 得分return;}}sc.close();}/*** 回溯函数，尝试将第index个得分分配给某个队员* @param index 当前正在分配的得分索引* @param buckets 每个队员当前的得分* @param target 每个队员的目标得分* @return 是否能够成功分配*/private static boolean canPartition(int index, int[] buckets, int target) {if(index == n) return true; // 所有得分都已分配int current = scores[index];for(int i =0; i < buckets.length; i++) {if(buckets[i] + current > target) continue; // 如果当前队员得分超过目标，跳过if(i >0 && buckets[i] == buckets[i-1]) continue; // 避免重复尝试buckets[i] += current; // 将当前得分分配给队员iif(canPartition(index +1, buckets, target)) return true; // 递归分配下一个得分buckets[i] -= current; // 回溯，撤销分配if(buckets[i] ==0) break; // 如果当前队员得分为0，后续队员也不会分配到得分}return false;}
}