4409: 盒子包裹问题
[Creator : ]
Description
某商城有卖空盒子,各种大小的正方形空盒子。对于第 $i\ (1 \leq i \leq n)$ 个盒子,它的边长为 $a_i$。
现在你要购买多个空盒子,快递打包的时候可以将他们嵌套打包,以节约成本。
如果满足以下三个条件,盒子 $i$ 可以放到盒子 $j$ 中,其中 $i \neq j$:
现在你要购买多个空盒子,快递打包的时候可以将他们嵌套打包,以节约成本。
如果满足以下三个条件,盒子 $i$ 可以放到盒子 $j$ 中,其中 $i \neq j$:
- 盒子 $i$ 没有放在另外一个盒子里
- 盒子 $j$ 不包含任何其他盒子
- $a_i < a_j$
Input
第一行包括一个整数 $n\ (1 \leq n \leq 100,000)$,表示购买盒子数量。
第二行包含了 $n$ 个整数 $a_1,a_2,...,a_n\ (1 \leq a_i \leq 10^9)$。
第二行包含了 $n$ 个整数 $a_1,a_2,...,a_n\ (1 \leq a_i \leq 10^9)$。
Output
一行一个整数,表示包裹的最小数量。
Sample 1 Input
4
4 2 4 3
Sample 1 Output
2
将第二个盒子放到第一个盒子中;
将第四个盒子放到第二个盒子中。
这样的方案是最少的。
将第四个盒子放到第二个盒子中。
这样的方案是最少的。
Sample 2 Input
3
5 5 5
Sample 2 Output
3
Sample 3 Input
8
1 2 3 4 5 6 7 8
Sample 3 Output
1
10
10 9 8 7 6 5 4 3 2 1
1