Skip to content

1015: 塔

题目

题目描述

奶牛们最讨厌黑暗。为了更换牛棚顶部的电灯泡,$Bessie$必须要用外面一捆捆的干草搭建一个塔爬上去,才能够得到。一共有$N(1 \le N \le 100,000)$捆干草,编号依次为$1~N$,它们按顺序放在传送带上运进牛棚里来,第i捆干草的宽度为$w_i(1 \le w_i \le 10,000)$,所有干草的长度和高度均为$1$。

建塔的时候Bessie必须要把这$N$捆干草都用上,并要按照它们被运进来的顺序安放,在建第一层(地基)的时候,她可以想放多少捆就放多少捆,必须把它们紧紧地码成一行。她可以把接下来的一些干草码在之前干草的上面以便新建一层,上面的层不能比它下面的层宽,使用这种方法堆叠,直到把所有的干草捆用光。注意,她必须按干草被运进来的顺序来码放它们,建塔的时候也必须从下往上一层一层地进行,比如,假定上一捆干草是放在第二层的,那以后的干草就不可以再放到第一层(即塔基)。

$Bessie$的目标是要尽可能建一个最高的塔,她事先知道每一捆被放在传送带上运进来的干草的宽度,那么,她究竟可以搭到多高呢?

输入格式

第$1$行,一个整数$N$;

第$2~N+1$行,第$i+1$行包含一个整数$w_i$;

输出格式

一行,一个整数表示答案,即最多可以建多高。

样例输入

3 1 2 3

样例输出

2

数据范围

$1 \le N \le 100,000$;

$1 \le w_i \le 10,000$.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!