问题重述

有 $N$ 种曲奇，第 $i$ 种有 $A_i$ 个。需要打包到盒子中，要求：

1. 每个盒子中的曲奇种类不同
2. 每个盒子中的曲奇数量必须是给定的 $B_1, B_2, \dots, B_M$ 中的一个

求是否能打包所有曲奇，并在可以时给出使用盒子数最少的方案。

---

关键观察

1. 问题本质

这是一个匹配问题：将曲奇分配到盒子中，每个盒子有容量限制且不能包含同种曲奇多次。

2. 必要条件

设总曲奇数为 $T = \sum A_i$，则：

• 必须有 $\sum$ (盒子容量) $\ge T$
• 每个盒子容量 $B_j$ 必须 $\le N$（因为最多放 $N$ 种不同曲奇）

3. 霍尔定理（Hall's Theorem）

对于此类匹配问题，霍尔定理给出充要条件：

对于任意曲奇种类的子集 $S$，其总数量 $\sum_{i \in S} A_i$ 必须 $\le$ 能覆盖这些曲奇的盒子的总容量。

---

核心解法

1. 可行性判断

关键思路：将问题看作二分图匹配

• 左部：曲奇种类（每种曲奇需要匹配 $A_i$ 次）
• 右部：盒子容量（每个盒子容量为某个 $B_j$）

使用网络流或贪心匹配判断可行性。

2. 最少盒子数

设 $f(x)$ = 是否能用 $x$ 个盒子装下所有曲奇。

单调性：如果 $x$ 个盒子可行，那么 $x+1$ 个盒子也可行（可以加空盒）。

因此可以二分答案，寻找最小的 $x$ 使得 $f(x) = \text{True}$。

3. 贪心匹配策略

对于固定的盒子数 $x$，我们可以：

1. 选择 $x$ 个盒子容量（可重复选择 $B_j$）
2. 将曲奇按数量从大到小排序
3. 将盒子容量从大到小排序
4. 贪心匹配：用最大的盒子装数量最多的曲奇

正确性：如果存在解，那么按数量降序匹配容量降序的盒子可以得到解。

---

算法框架

1. 预处理

1. 将曲奇按 $A_i$ 降序排序
2. 将可用盒子容量 $B_j$ 排序

2. 二分答案

二分盒子数量 $x$，检查是否可行：

def check(x):
    # 选择 x 个最大的盒子容量
    boxes = select_largest_boxes(x)
    cookies = sorted_A_descending
    
    # 贪心匹配
    for box_cap in boxes:
        remaining = box_cap
        for i in range(len(cookies)):
            if cookies[i] > 0 and remaining > 0:
                take = min(cookies[i], remaining)
                cookies[i] -= take
                remaining -= take
        # 如果还有剩余容量，说明匹配失败
        if remaining > 0 and all(c == 0 for c in cookies):
            return False
    
    return all(c == 0 for c in cookies)

3. 构造方案

找到最小 $x$ 后，实际执行贪心匹配并记录分配方案。

---

优化技巧

1. 快速可行性检查

不需要实际模拟，可以用以下方法快速检查：

设曲奇数量降序为 $a_1 \ge a_2 \ge \dots \ge a_N$ 设盒子容量降序为 $b_1 \ge b_2 \ge \dots \ge b_x$

必要条件：对于所有 $k$，$\sum_{i=1}^k a_i \le \sum_{j=1}^k b_j$

这是著名的 "Gale-Ryser" 定理的变形。

2. 复杂度优化

• 二分答案：$O(\log N)$ 次检查
• 每次检查：$O(N \log N)$ 排序
• 总复杂度：$O(N \log^2 N)$，适合 $N \le 15000$

---

具体实现细节

1. 可行性检查算法

def is_feasible(x, A, B):
    # 选择 x 个最大的盒子容量
    boxes = sorted(B, reverse=True)[:x]
    cookies = sorted(A, reverse=True)
    
    # 检查前缀和条件
    prefix_cookies = 0
    prefix_boxes = 0
    for k in range(min(len(cookies), len(boxes))):
        prefix_cookies += cookies[k]
        prefix_boxes += boxes[k]
        if prefix_cookies > prefix_boxes:
            return False
    
    # 检查总数条件
    return sum(cookies) <= sum(boxes)

2. 构造方案

找到最小 $x$ 后：

1. 维护每个曲奇种类的剩余数量
2. 对每个盒子（按容量降序）：
   • 选择剩余数量最多的曲奇种类
   • 尽可能多地放入该盒子
   • 记录分配情况

---

边界情况处理

1. 无解情况

• 总曲奇数 > 最大盒子容量 × 可用盒子数
• 某种曲奇数量 > 最大盒子容量
• 霍尔条件不满足

2. 特殊数据

• 所有 $A_i = 1$：退化为普通匹配
• $M = 1$：所有盒子容量相同

---

复杂度分析

• 排序：$O(N \log N)$
• 二分答案：$O(\log N)$ 次检查
• 每次检查：$O(N \log N)$
• 总复杂度：$O(N \log^2 N)$
• 空间复杂度：$O(N)$

---

总结

这道题的核心在于：

1. 问题识别：识别出这是带容量限制的二分图匹配问题
2. 霍尔定理应用：使用组合优化理论判断可行性
3. 贪心策略：用最大的盒子装最多的曲奇
4. 二分优化：通过二分查找最小盒子数

通过将实际问题抽象为图论匹配模型，并利用组合优化的经典理论，我们得到了一个高效且正确的解法。