← 返回题目列表

AtCoder · arc006_3

C. 堆叠

中文机器翻译题面 查看原题

問題文

 由于高桥现已成年,他决定离开父母独自生活。我想把纸板箱从卡车运到我要搬去的房间,但如果房间的地板上铺满了纸板箱,我今天就找不到高桥睡觉的蒲团了。
 所以,1 我决定制作一堆纸板箱,而不是一个接一个地摊开盒子。然而,纸板有固定的重量,如果你在上面堆放比下面的纸板重的纸板,下面的纸板就会塌陷。
图表:底部纸板的重量必须大于顶部纸板的重量

 纸板箱的重量是按照从卡车上运输的顺序给出的,因此请考虑如何以不会压坏纸板箱的方式堆放纸板箱。然后,求堆积的山的数量最少时的山的数量。 有一条

入力

输入是按以下格式从标准输入给出的。
N
w_1
w_2
:
:
w_N
  • 输入是 N+1 行。
  • 1 行包含一个表示纸板箱数量的整数。 来自行 N(1≦N≦50) 。 来自行
  • 2 从线 N 行包含 上线i+1(1≦i≦N) 在行中 i 表示要承载的纸板重量的整数。 w_i(1≦w_i≦100,000) 。 来自行

出力

按顺序搬运纸板箱并将其堆叠以使顶部纸板箱的重量与底部纸板箱的重量相同或小于底部纸板箱的重量时,可创建的纸板箱堆的最小数量将作为标准输出输出。 输出为 1 行。
请在末尾输出换行符。

入力例 1

5
4
3
1
2
1

出力例 1

2
  • 如果按照下例所示的顺序堆叠它们,2 将创建两堆纸板。
  • 3 旁边纸箱的重量 2 纸板不能堆放在上面,所以 1 不能是一堆,最小为 2 变为。

入力例 2

7
93
249
150
958
442
391
25

出力例 2

3
  • 当按照下图所示的形状堆叠时,山的数量为 3 变为。
  • 更正:下图中的225纸板箱是25错误。非常抱歉。

入力例 3

4
100
100
100
100

出力例 3

1
  • 相同重量的纸板箱可以堆叠在一起,因此1 可制成一堆。

入力例 4

6
5
10
15
20
25
30

出力例 4

6
  • 由于没有一个纸板箱可以堆叠在前一个纸板箱之上,1 我无法将它们全部堆叠在一起。
  • 因此,6 一座山是最少的。

入力例 5

15
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9

出力例 5

6
  • 如下图所示堆叠时,变为最小值。