题面描述

某码头有一批集装箱，每个集装箱形状大小一致。由于材质不同，每个集装箱上方可堆叠的集装箱个数不同。具体规则如下：

标号为 $0$ 的集装箱，不能在其上方放置任何集装箱；
标号为 $1$ 的集装箱，其上方最多可放置 $1$ 个集装箱；
标号为 $n$ （ $0 \leq n \leq 10^6$ ）的集装箱，其上方最多可放置 $n$ 个集装箱。

给定一批集装箱，假设每个集装箱的底面积为 $1$ ，要求通过合理堆叠使得占地面积（即堆垛的数量）最小，并输出最小的占地面积。

P2612.集装箱堆叠

1000ms

Tried: 226

Accepted: 62

Difficulty: 5

所属公司 : 华为

算法与标签>贪心算法

题目内容

描述:某码头有一批集装箱,每个集装箱形状大小一致。

由于材质不同，每个集装箱上方可堆叠的集装箱个数不同。如: 标号 $0$ 的集装箱，则不可在其上方放置集装箱;

标号 $1$ 的集装箱，其上方最多可放置 $1$ 个集装箱;

标号 $n$ ( $0<=n<=10^6$ )的集装箱，其上方最多可放置 $n$ 个集装箱;

给定一批集装箱，假设每个集装箱底面积为 $1$ ，求如何堆叠使得占地面积最小，并输出最小面积。

输入描述

输入为一行整形数组的字符串，每个数字以空格隔开:

示例: $a1\ a2\ a3... an$

其中 $0<n<=10^4$ , $0<=ai<=10^6$ 表示集装箱的标号;

输入保证正确性，不需要做额外校验

输出描述

$int$ 值，最小面积

样例1

输入

0 2 1

输出

说明

最少可堆叠为 $1$ 垛，堆叠顺序自下而上依次为:标号 $2$ 集装箱、标号 $1$ 集装箱、标号 $0$ 集装箱。

样例2

输入

1 2 1 2

输出

说明

最少可堆叠为 $2$ 垛。

堆叠方法 $1$ :

第 $1$ 垛自下而上依次为: $2\ 1\ 1$ ;

第 $2$ 垛自下而上依次为: $2$ ;

堆叠方法 $2$ :

第 $1$ 垛自下而上依次为: $2\ 2\ 1$ ;

第 $2$ 垛自下而上依次为: $1$ ;

堆叠方法 $3$ :

第 $1$ 垛自下而上依次为: $2\ 1\ 2$ ;

第 $2$ 垛自下而上依次为: $1$ ;

输入

预期输出（选填）

题面描述

P2612.集装箱堆叠

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About