题面描述

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

可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同。

然而比赛过程中的每 $1$ 分钟的得分都只能由某一个人包揽。

思路

本题要求将给定的得分列表分配给尽可能多的队员，使得每个队员的得分相同。要达到这一目标，我们需要：

1. 最大化队员数目：即找到最大的可能的 $k$，使得总得分可以被 $k$ 整除，并且能够将得分分配给 $k$ 个队员，每个队员的得分都等于总得分除以 $k$。

2. 分割得分列表：检查是否可以将得分列表分割成 $k$ 个子集，每个子集的和都等于目标得分 $S = \text{总得分} / k$。

具体步骤如下：

1. 计算总得分 $T$。
2. 从最大的可能的队员数 $k = t$ 开始，依次递减。
3. 对于每个 $k$，检查 $T$ 是否能被 $k$ 整除，即 $S = T / k$ 是整数。
4. 如果能整除，则尝试将得分列表分割成 $k$ 个和为 $S$ 的子集。
5. 如果成功分割，则输出 $S$，因为我们从最大的 $k$ 开始，$S$ 会是最小的可能值。

由于输入规模较小（$t \leq 50$），可以使用回溯法进行子集划分。

cpp

#include <bits/stdc++.h>
using namespace std;

// 回溯函数尝试为每个子集分配得分
bool backtrack(vector<int>& nums, vector<int>& subsetSums, int target, int k, int start) {
    if (k == 0) return true; // 所有子集都已成功分配
    if (subsetSums[k - 1] == target) { // 当前子集已达到目标，开始分配下一个子集
        return backtrack(nums, subsetSums, target, k - 1, 0);
    }
    for (int i = start; i < nums.size(); ++i) {
        if (subsetSums[k - 1] + nums[i] > target) continue; // 剪枝：当前得分超过目标
        if (i > start && nums[i] == nums[i - 1]) continue; // 去重
        subsetSums[k - 1] += nums[i];
        if (backtrack(nums, subsetSums, target, k, i + 1)) return true;
        subsetSums[k - 1] -= nums[i];
    }
    return false;
}

// 检查是否可以将 nums 分割成 k 个子集，每个子集的和为 target
bool canPartitionKSubsets(vector<int>& nums, int k, int target) {
    int n = nums.size();
    vector<int> subsetSums(k, 0);
    // 从最大的得分开始分配，先处理大的数可以更快剪枝
    sort(nums.begin(), nums.end(), greater<int>());
    // 如果最大的数超过目标，则不可能分配
    if (nums[0] > target) return false;
    return backtrack(nums, subsetSums, target, k, 0);
}

int main(){
    int t;
    cin >> t;
    vector<int> p(t);
    for(auto &x:p) cin >> x;
    // 计算总得分
    int total = accumulate(p.begin(), p.end(), 0);
    // 从最大的可能队员数开始，寻找最小的 MVP 得分
    for(int k = t; k >=1; --k){
        if(total % k !=0) continue; // 总得分必须能被 k 整除
        int target = total / k;
        // 检查是否可以分割成 k 个子集，每个子集和为 target
        if(canPartitionKSubsets(p, k, target)){
            cout << target;
            return 0;
        }
    }
    return 0;
}

python

from typing import List

def can_partition(nums: List[int], k: int, target: int) -> bool:
    nums.sort(reverse=True)  # 先排序，优化剪枝
    subsets = [0] * k

    def backtrack(index):
        if index == len(nums):
            return True
        current = nums[index]
        for i in range(k):
            if subsets[i] + current > target:
                continue
            if i > 0 and subsets[i] == subsets[i-1]:
                continue
            subsets[i] += current
            if backtrack(index + 1):
                return True
            subsets[i] -= current
        return False

    return backtrack(0)

def main():
    t, *rest = map(int, open(0).read().split())
    p = rest[:t]
    total = sum(p)
    for k in range(t, 0, -1):
        if total % k !=0:
            continue
        target = total // k
        if can_partition(p, k, target):
            print(target)
            return

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    public static boolean canPartition(int[] nums, int k, int target) {
        Arrays.sort(nums);
        // 从大到小排序
        for(int i=0; i<nums.length/2; i++){
            int temp = nums[i];
            nums[i] = nums[nums.length-1-i];
            nums[nums.length-1-i] = temp;
        }
        int[] subsets = new int[k];
        return backtrack(nums, subsets, 0, target);
    }

    private static boolean backtrack(int[] nums, int[] subsets, int index, int target){
        if(index == nums.length){
            for(int i=0; i<subsets.length; i++) {
                if(subsets[i] != target) return false;
            }
            return true;
        }
        for(int i=0; i<subsets.length; i++){
            if(subsets[i] + nums[index] > target) continue;
            if(i >0 && subsets[i] == subsets[i-1]) continue;
            subsets[i] += nums[index];
            if(backtrack(nums, subsets, index+1, target)) return true;
            subsets[i] -= nums[index];
        }
        return false;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[] p = new int[t];
        for(int i=0; i<t; i++) p[i] = sc.nextInt();
        int total = 0;
        for(int num : p) total += num;
        // 从最大的可能队员数开始，寻找最小的 MVP 得分
        for(int k = t; k >=1; k--){
            if(total % k !=0) continue;
            int target = total / k;
            if(canPartition(p, k, target)){
                System.out.println(target);
                return;
            }
        }
    }
}

题目描述

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

可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，

然而比赛过程中的每 $1$ 分钟的得分都只能由某一个人包揽。

输入描述

输入第一行为一个数字 $t$ ，表示为有得分的分钟数

$1 ≤ t ≤ 50$

第二行为 $t$ 个数字，代表每一分钟的得分 $p$，

$1 ≤ p ≤ 50$

输出描述

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

样例1

输入

9
5 2 1 5 2 1 5 2 1

输出

6

说明

样例解释 一共 $4$ 人得分，分别都是 $6$ 分

$5 + 1 ， 5 + 1 ， 5 + 1 ， 2 + 2 + 2$