NZIC 2026 Round 1（新西兰信息学竞赛 2025 第一轮）

C.Carpentry（木工）

输入： 标准输入（stdin） 输出： 标准输出（stdout） 内存限制： 64 MB 时间限制： 1.0 秒

• problem statement
• submit
• submissions

---

题目描述

住在荒野里确实很不错，但你那座老木屋已经非常需要升级了，所以你决定在原有结构上再加盖一层。

当然，要到达第二层，你需要建造一组楼梯。

你已经挑选出了：

$$N$$

根非常适合制作楼梯的原木，每根原木都有一个高度。

一组楼梯由一系列原木组成，其中：

• 第 1 根原木的高度必须是 1；
• 第 2 根原木的高度必须是 2；
• ……
• 依次类推，直到最高一级。

你可以使用斧头把任意一根原木削短任意高度，并把削下来的部分丢掉。

给定这 (N) 根原木各自的高度，你想知道：

最多能够建出多高的楼梯？

---

输入格式

第一行包含一个整数：

N

第二行包含 (N) 个用空格分隔的整数：

h0 h1 ... h(n-1)

其中：

$$h_i$$

表示第 (i) 根原木的高度。

---

输出格式

输出一个整数：

使用现有原木能够建造出的楼梯的最大高度。

---

数据范围

$$1\le N\le100000$$ $$1\le h_i\le10^9$$

---

子任务

• 子任务 1（10%）：

$$N=3$$

• 子任务 2（10%）：

$$h_i\le5$$

• 子任务 3（20%）：

$$N\le1000$$

• 子任务 4（60%）：

没有额外限制。

---

样例说明

样例 1

你有 3 根原木，每根高度都是：

$$2$$

你可以把其中第一根原木削短到高度：

$$1$$

然后，用这根高度为 1 的原木，以及另一根高度为 2 的原木，组成一组高度为：

$$2$$

的楼梯。

---

样例 2

如果把第 3 根原木的高度从 4 削短到 3，那么就可以得到：

[1, 2, 3]

因此能够组成一组高度为：

$$3$$

的楼梯。

---

样例输入 1

3
2 2 2

样例输出 1

2

---

样例输入 2

3
1 2 4

样例输出 2

3

测试点编号	数据层级	N	数据特征	主要覆盖点	标准输出
1	弱数据	1	单元素且值为 0	最小规模、无法满足 need=1	0
2		5	所有元素均为 1	大量重复值、同一数值不能反复提升答案	1
3	正常数据	8	乱序，含重复值和较大值	排序、跳过无效重复值、贪心连续匹配	6
4		10	含负数、零、重复值和数值间隔	无效小值、断层数据及后续大值补位	7
5	极限数据	20	含 long long 最小值、最大值及超大正数	64 位整数边界、极端值排序和混合数据	16