XLII 保加利亚国家信息学奥林匹克竞赛

地区赛，2026 年 2 月 14 日 C 组（7–8 年级）

---

题目 C1：花瓶（VASES / ВАЗИ）

时间限制： 1.2 秒 内存限制： 256 MB 作者： Velislav Garkov（韦利斯拉夫·加尔科夫）、Dobrin Bashev（多布林·巴舍夫）、Rumen Mihov（鲁门·米霍夫）

---

题目背景

鲍比·瓦齐米罗夫是一位著名的陶艺家。最近灵感爆棚，做出了太多花瓶，已经没有地方存放了。 因此他决定在工作室的一面墙上安装一个带**多个横向隔层（搁板）**的柜子，用来放花瓶。

他有 (N) 个花瓶，高度分别为 $(A_1, A_2, \dots, A_N)$。所有花瓶的直径（宽度）都相同，均为 ​1​。

柜子要安装的那面墙总高度为 ​**(H)​。鲍比可以放置任意数量的​水平搁板**​：

• 每块搁板横向覆盖整个柜子的宽度（从左到右）。
• 搁板可以放在任意高度，因此相邻搁板之间形成的隔层高度可以不同。
• 所有隔层高度之和​**不超过 (H)**​。
• 可以认为搁板厚度忽略不计。

放置规则：

• 一个花瓶可以放入某个隔层，当且仅当该隔层高度 ≥ 花瓶高度。
• 同一个隔层内可以并排放置多个花瓶（因为每个花瓶宽度为 1，所以一个隔层能放多少个取决于柜子总宽度）。

鲍比希望柜子的​宽度尽可能小​，但他太忙了，于是请你帮忙： 求能放下所有花瓶的柜子的​最小可能宽度​。

---

任务

编写程序 vases，计算上述最小宽度。

---

输入格式

第一行输入两个正整数：

N H

分别表示花瓶数量和墙（柜子）的最大高度。

第二行输入 (N) 个整数：

A1 A2 ... AN

表示每个花瓶的高度。

---

输出格式

输出一行一个整数： 表示能容纳所有花瓶的柜子的​最小宽度​。

---

数据范围

• $(1 \le N \le 10^7)$
• $(1 \le H \le 10^7)$
• $(1 \le A\_i \le H)$

---

子任务

子任务	分值	需要通过的前置子任务	(N) 上限	其他限制
0		—	—	样例测试
1	7		≤ (10^3)	所有 (A_i) 都相等
2	14			—
3	15	0–2		仅有两种不同的 (A_i)
4	35	0–3	≤ (10^5)	—
5	29	0–4	≤ (10^7)

说明：子任务得分只有在通过该子任务及其要求的前置子任务全部测试后才能获得。

---

样例

输入：

8 7
2 1 1 3 2 4 1 1

输出：

3

样例说明： 可参考题目配图： 黄色花瓶高度为 1，绿色高度为 2，红色高度为 3，蓝色高度为 4。

---