2023华为OD机试真题【星际篮球争霸赛/动态规划】_2023华为od机试真题 星际篮球争霸赛

题目描述

在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个人都能拿到MVP，MVP的条件是单场最高分得分获得者。可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，
然而比赛过程中的每1分钟的得分都只能由某一个人包揽。输出有得分的队员都是MVP时，最少得MVP得分。
输入描述
输入第一行为一个数字 t，表示为有得分的分钟数 1 ≤ t ≤ 50
第二行为 t 个数字，代表每一分钟的得分 p， 1 ≤ p ≤ 50
输出描述
输出有得分的队员都是MVP时，最少得MVP得分。
示例1：
输入：
9
5 2 1 5 2 1 5 2 1
输出：
6
说明：
4人MVP，每个人都是6分。

解题思路

这道题应该是用动态规划解题。首先从分钟数开始递减，尝试将总得分平均分成k份，使得每份得分相等。使用动态规划来检查是否可以将数组分成k个子集，其中每个子集的和=总和/k。如果找到满足条件的k值，输出总和除以k，即为最少的MVP得分。

参考代码

import java