B. 汽车销售员卡尔 详细题解

1. 问题理解

• 有 $n$ 种车型，第 $i$ 种有 $a_i$ 辆车。
• 每个顾客最多可以买 $x$ 辆车，且必须来自不同车型。
• 目标：找到最少的顾客数量，使得所有车都能被卖出。

---

2. 关键观察

观察 1：单种车型的限制

由于每个顾客不能从同一车型买超过 $1$ 辆车，所以对于第 $i$ 种车型，它需要至少 $a_i$ 个顾客（每个顾客最多贡献 $1$ 辆）。

因此，最少顾客数至少为：

$$\max_{1 \le i \le n} a_i$$

观察 2：总车辆数的限制

每个顾客最多买 $x$ 辆车，所以总顾客数至少需要：

$$\left\lceil \frac{\sum_{i=1}^n a_i}{x} \right\rceil $$

观察 3：下界

结合两个约束，最少顾客数至少为：

$$\text{lower} = \max\left( \max_i a_i,\ \left\lceil \frac{\sum a_i}{x} \right\rceil \right) $$

---

3. 充分性证明

这个下界是否总是可以达到？答案是是的。

证明思路（网格填充法）

设 $w = \max\left( \max_i a_i,\ \left\lceil \frac{S}{x} \right\rceil \right)$，其中 $S = \sum a_i$。

构造一个 $w \times x$ 的网格：

• $w$ 行代表 $w$ 个顾客
• $x$ 列代表每个顾客最多可以买 $x$ 辆车

将汽车按车型依次放入网格中，逐列填充（即先填第 $1$ 列的所有行，再填第 $2$ 列，以此类推）：

1. 对于第 $i$ 种车型的 $a_i$ 辆车，将它们放入网格中连续的空位中。
2. 由于 $w \ge \max_i a_i$，每种车型的车都能放在同一列的不同行中（因为每列有 $w$ 行）。
3. 由于 $w \ge \lceil S/x \rceil$，网格的总格子数 $w \times x \ge S$，所以所有车都能放下。
4. 最终，每行（每个顾客）最多有 $x$ 辆车，且每行的车都来自不同车型（因为同一车型的车都在同一列）。

因此，$w$ 个顾客就足够了。

---

4. 算法步骤

1. 读入 $n$ 和 $x$。
2. 读入数组 $a$，同时计算：
   • maximo = $\max a_i$
   • sum = $\sum a_i$
3. 计算 sec = $\lceil sum / x \rceil$，即 $(sum + x - 1) / x$。
4. 输出 max(maximo, sec)。

---

5. 时间复杂度

• 每个测试用例 $O(n)$
• $t \le 10^4$，$\sum n \le 5 \times 10^5$，完全可行

---

6. 示例验证

示例 1：$n=3, x=2, a=[3,1,2]$

• maximo = 3
• sum = 6，sec = ceil(6/2) = 3
• max(3, 3) = 3 ✅

示例 2：$n=3, x=3, a=[2,1,3]$

• maximo = 3
• sum = 6，sec = ceil(6/3) = 2
• max(3, 2) = 3 ✅

示例 3：$n=5, x=3, a=[2,2,1,9,2]$

• maximo = 9
• sum = 16，sec = ceil(16/3) = 6
• max(9, 6) = 9 ✅

示例 4：$n=7, x=4, a=[2,5,3,3,5,2,5]$

• maximo = 5
• sum = 25，sec = ceil(25/4) = 7
• max(5, 7) = 7 ✅

---

7. 二分查找的替代解法

虽然本题有直接公式，但也可以使用二分查找：

• 二分答案 $mid$，判断是否能用 $mid$ 个顾客卖完所有车。
• 检查条件：
  1. $mid \ge \max_i a_i$（否则某种车型卖不完）
  2. $mid \times x \ge \sum a_i$（否则总容量不足）
• 时间复杂度 $O(n \log M)$，其中 $M$ 是答案的上界。

---

8. 总结

最终公式：

$$\text{ans} = \max\left( \max_i a_i,\ \left\lceil \frac{\sum a_i}{x} \right\rceil \right) $$

核心思想：

1. 每个顾客最多买 $x$ 辆，且不能买同型号两辆
2. 答案至少是最大型号的数量
3. 答案至少是总车辆数除以 $x$ 的上取整
4. 这两个下界同时满足时，构造可以证明其充分性