问题 4295 --4. 装箱问题

4295: 4. 装箱问题

题目描述

  社会实践是小学教育的重要组成部分,也是素质教育的一个重要环节,老师经常带同学们到工厂车间去参观。一天,在班主任的带领下,小明和他的同学来到了一间生产箱子的工厂,在工厂的仓库里有许多箱子,这些箱子被排成单独的一行,每个箱子都有一个体积,箱子的体积不大于1000个单位体积,体积小的可以放到体积大的箱子里面。仓库的经理想把一些箱子放进另一些箱子里面,以便使得左端有更多连续的空余位置。

基于安全因素的考虑,一个箱子最多能够装下一个比它小的箱子,并且只能尝试将左端的前K个箱子装入与之相邻的K(即K+1~2*K之间)个箱子中。

你的任务是帮助经理计算一下,在满足安全因素的情况下,左端有多少个箱子可以装入与之相邻的箱子中。

输入

输入文件pack.in的第一行为一个整数N,表示箱子的总个数。第二行是N个整数,表示这N个箱子的尺寸。

输出

输出文件pack.out为一个整数,表示左边有多少个箱子可以装入与之相邻的箱子中,即题目中的最大的K值。

样例输入输出

输入#1 复制
10
2 2 1 4 3 2 5 4 2 3
输出#1 复制
4

提示

【样例解释】
      前4个箱子可以放入5~8个箱子中。 其中一种放法为,第1箱子装入第5个箱子中,第2个箱子装入第8个箱子中,第3个箱子装入第6个箱子中,第4个箱子装入第7个箱子中,这样左边最多可以空出4个箱子位置,除此之外,没有其它方式能使左边空出更多的位置。
   
【数据规模】
60%的数据N<=300
100%的数据N<=3000

序号 标题 作者 发表时间 费用 订购数 操作