Hard
题目描述
有一个甜甜圈商店，每次烘焙 batchSize 个甜甜圈。他们有一个规则，必须在供应下一批甜甜圈之前，先把当前批次的甜甜圈全部供应完。
给你一个整数 batchSize 和一个整数数组 groups，其中 groups[i] 表示有一组 groups[i] 个顾客会来到商店。每个顾客都会得到恰好一个甜甜圈。
当一组顾客来到商店时，必须在为下一组顾客服务之前为该组的所有顾客服务。如果一组顾客都能得到新鲜的甜甜圈，那么这组顾客就是快乐的。也就是说，该组的第一个顾客没有收到上一组剩下的甜甜圈。
你可以自由地重新安排组的顺序。返回重新安排组后可能的最多快乐组数。
示例 1：
输入：batchSize = 3, groups = [1,2,3,4,5,6]
输出：4
解释：你可以将组安排为 [6,2,4,5,1,3]。那么第 1、2、4、6 组将是快乐的。
示例 2：
输入：batchSize = 4, groups = [1,3,2,5,2,2,1,6]
输出：4
提示：
1 <= batchSize <= 91 <= groups.length <= 301 <= groups[i] <= 10^9
解题思路
解题思路
这是一个经典的状态压缩动态规划问题。核心思想是将问题转化为分割问题：将所有组分割成若干个分区，使得每个分区内的顾客总数能被 batchSize 整除。
关键观察
- 只有余数重要：对于每个组，我们只关心其大小模
batchSize的余数 - 频率统计：统计每种余数出现的频次
- 配对优化：余数为
r的组可以和余数为batchSize - r的组配对，形成一个完整的快乐分区
算法步骤
- 预处理配对：将可以直接配对的组先处理掉（如余数互补的组）
- 状态压缩DP：使用频率数组的哈希值作为状态，记录当前剩余余数和对应的最大快乐组数
- 状态转移：对于每种余数，尝试取出一个组，更新状态
复杂度分析
- 时间复杂度：O(batchSize^groups.length)，但由于预处理和剪枝，实际运行时间会小很多
- 空间复杂度：O(状态数量)，用于记忆化
这种方法充分利用了 batchSize ≤ 9 这个限制，使得状态空间可控。
代码实现
class Solution {
public:
int maxHappyGroups(int batchSize, vector<int>& groups) {
vector<int> freq(batchSize, 0);
int result = 0;
// 统计每种余数的频次
for (int group : groups) {
freq[group % batchSize]++;
}
// 余数为0的组天然快乐
result += freq[0];
freq[0] = 0;
// 配对处理互补的余数
for (int i = 1; i <= batchSize / 2; i++) {
if (i == batchSize - i) {
result += freq[i] / 2;
freq[i] %= 2;
} else {
int pairs = min(freq[i], freq[batchSize - i]);
result += pairs;
freq[i] -= pairs;
freq[batchSize - i] -= pairs;
}
}
unordered_map<string, int> memo;
return result + dfs(freq, 0, batchSize, memo);
}
private:
int dfs(vector<int>& freq, int remainder, int batchSize, unordered_map<string, int>& memo) {
string key = to_string(remainder) + "#";
for (int f : freq) {
key += to_string(f) + ",";
}
if (memo.count(key)) {
return memo[key];
}
int maxVal = 0;
for (int i = 1; i < batchSize; i++) {
if (freq[i] > 0) {
freq[i]--;
int newRemainder = (remainder + i) % batchSize;
int gain = (remainder == 0) ? 1 : 0;
maxVal = max(maxVal, gain + dfs(freq, newRemainder, batchSize, memo));
freq[i]++;
}
}
return memo[key] = maxVal;
}
};
class Solution:
def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
freq = [0] * batchSize
result = 0
# 统计每种余数的频次
for group in groups:
freq[group % batchSize] += 1
# 余数为0的组天然快乐
result += freq[0]
freq[0] = 0
# 配对处理互补的余数
for i in range(1, batchSize // 2 + 1):
if i == batchSize - i:
result += freq[i] // 2
freq[i] %= 2
else:
pairs = min(freq[i], freq[batchSize - i])
result += pairs
freq[i] -= pairs
freq[batchSize - i] -= pairs
memo = {}
def dfs(freq_tuple, remainder):
if freq_tuple in memo:
return memo[freq_tuple]
freq_list = list(freq_tuple)
max_val = 0
for i in range(1, batchSize):
if freq_list[i] > 0:
freq_list[i] -= 1
new_remainder = (remainder + i) % batchSize
gain = 1 if remainder == 0 else 0
max_val = max(max_val, gain + dfs(tuple(freq_list), new_remainder))
freq_list[i] += 1
memo[freq_tuple] = max_val
return max_val
return result + dfs(tuple(freq), 0)
public class Solution {
public int MaxHappyGroups(int batchSize, int[] groups) {
int[] freq = new int[batchSize];
int result = 0;
// 统计每种余数的频次
foreach (int group in groups) {
freq[group % batchSize]++;
}
// 余数为0的组天然快乐
result += freq[0];
freq[0] = 0;
// 配对处理互补的余数
for (int i = 1; i <= batchSize / 2; i++) {
if (i == batchSize - i) {
result += freq[i] / 2;
freq[i] %= 2;
} else {
int pairs = Math.Min(freq[i], freq[batchSize - i]);
result += pairs;
freq[i] -= pairs;
freq[batchSize - i] -= pairs;
}
}
Dictionary<string, int> memo = new Dictionary<string, int>();
return result + Dfs(freq, 0, batchSize, memo);
}
private int Dfs(int[] freq, int remainder, int batchSize, Dictionary<string, int> memo) {
string key = remainder + "#" + string.Join(",", freq);
if (memo.ContainsKey(key)) {
return memo[key];
}
int maxVal = 0;
for (int i = 1; i < batchSize; i++) {
if (freq[i] > 0) {
freq[i]--;
int newRemainder = (remainder + i) % batchSize;
int gain = remainder == 0 ? 1 : 0;
maxVal = Math.Max(maxVal, gain + Dfs(freq, newRemainder, batchSize, memo));
freq[i]++;
}
}
memo[key] = maxVal;
return maxVal;
}
}
var maxHappyGroups = function(batchSize, groups) {
const counts = new Array(batchSize).fill(0);
let result = 0;
for (let group of groups) {
counts[group % batchSize]++;
}
result += counts[0];
counts[0] = 0;
for (let i = 1; i <= Math.floor(batchSize / 2); i++) {
if (i === batchSize - i) {
result += Math.floor(counts[i] / 2);
counts[i] %= 2;
} else {
const pairs = Math.min(counts[i], counts[batchSize - i]);
result += pairs;
counts[i] -= pairs;
counts[batchSize - i] -= pairs;
}
}
const memo = new Map();
function dfs(state, remainder) {
const key = state.join(',') + ',' + remainder;
if (memo.has(key)) return memo.get(key);
let maxHappy = 0;
let hasGroups = false;
for (let i = 1; i < batchSize; i++) {
if (state[i] > 0) {
hasGroups = true;
state[i]--;
const newRemainder = (remainder + i) % batchSize;
const happy = (remainder === 0 ? 1 : 0) + dfs(state, newRemainder);
maxHappy = Math.max(maxHappy, happy);
state[i]++;
}
}
if (!hasGroups) maxHappy = 0;
memo.set(key, maxHappy);
return maxHappy;
}
result += dfs(counts, 0);
return result;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(batchSize^n) | n为剩余未配对的组数，实际由于剪枝效果较好 |
| 空间复杂度 | O(状态数量) | 记忆化存储的状态数量，最坏情况下为指数级 |