題目描述

在星球爭霸籃球賽對抗賽中，最大的宇宙戰隊希望每個人都能拿到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

說明：
一共 4 人得分，分別都是 6 分：5 + 1，5 + 1，5 + 1，2 + 2 + 2

解題思路

這是一個數組劃分問題，目標是將給定的分數數組分成若干個子集，使得每個子集的和都相等，且子集數量盡可能多（MVP人數最多），這樣每個MVP的得分就最小。

算法思路

1. 貪心策略：為了讓MVP人數最多，需要讓每個MVP的得分盡可能小
2. 枚舉驗證：從最大可能的MVP人數開始嘗試，逐步減少直到找到可行解
3. 回溯分組：使用回溯算法將分數分配到不同的組中，每組代表一個MVP

核心步驟

1. 計算總分，降序排列數組
2. 從最大MVP人數開始枚舉
3. 對每個人數，檢查總分能否整除
4. 使用回溯算法驗證是否能平均分組
5. 返回第一個可行方案的單人得分

代碼實現

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 Truefor i in range(len(groups)):if groups[i] + arr[index] <= target:groups[i] += arr[index]if dfs(arr, groups, index + 1, target):return Truegroups[i] -= arr[index]if groups[i] == 0:breakreturn Falsen = 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 // targetgroups = [0] * group_countif dfs(arr, groups, 0, target):print(target)break

算法要點

核心思想：

• 將數組分成k個和相等的子集，使k盡可能大
• 使用回溯算法將元素分配到不同組中
• 從最優解開始搜索，找到第一個可行解

剪枝優化：

1. 相同組剪枝：相同容量的組只嘗試第一個
2. 空組剪枝：如果空組放不下，跳過后續空組
3. 預處理：先處理等于目標值的元素
4. 排序優化：大元素優先處理，便于剪枝

復雜度分析

• 時間復雜度：O(k^n)，k為組數，n為元素個數
• 空間復雜度：O(k)，用于存儲各組當前和

解題總結

MVP爭奪戰本質上是數組劃分問題，通過貪心策略確定搜索方向，回溯算法驗證可行性，結合多種剪枝技巧提高效率。關鍵是理解問題的數學本質：尋找最大的k值，使得數組能被分成k個和相等的子集。