← 返回题目

题库练习盒子

← 上一题下一题 →

A71607 | $盒子$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

小 Y 有 n 个盒子，第 i 个盒子的大小是 a[i], 小 Y 保证 a[i] 一定是 2 的若干次方，比如 1,2,4,8,16,32,64,128,512,1024\dots\dots ，一个大小为 a[i] 的盒子的容量是 a[i]/2 ，就是说它可以装下总大小不超过 a[i]/2 的其他盒子，特别地，大小为 1 的盒子不能装下其他盒子。并且，装在盒子里的盒子也可以装其他盒子，比如，大小为 8 的盒子可以装下一个大小为 4 的盒子且大小为 4 的盒子事先已经装了一个大小为 2 的盒子。 现在小 Y 想知道，最少能有多少个不被其他盒子装下的盒子？

输入格式

第一行 1 个正整数 n ，表示盒子的数量。 第二行 n 个正整数 a[i] ，表示每个盒子的大小，保证 a[i] 一定是 2 的若干次方。

输出格式

一行一个正整数表示最少能有多少个不被其他盒子装下的盒子。

输入输出样例

输入 #1

5
1 2 1 1 8

输出 #1

输入 #2

3
1 1 1

输出 #2

输入 #3

6
1 1 1 4 1 2

输出 #3

C++ 编辑器

输入

输出