[常州市赛 2024] 盒子

Luogu
IDLGB4228
Time1000ms
Memory512MB
DifficultyP2
贪心2024江苏排序双指针 two-pointer科创活动小学活动
小 Y 有 $n$ 个盒子,第 $i$ 个盒子的大小是 $a_i$,小 Y 保证 $a_i$ 一定是 $2$ 的若干次方,比如 $1,2,4,8,16,32,64,128,256,512,1024\cdots$,一个大小为 $a_i$ 的盒子的容量是 $\dfrac{a_i}2$,就是说它可以装下总大小不超过 $\dfrac{a_i}2$ 的其他盒子,特别地,大小为 $1$ 的盒子不能装下其他盒子。并且,装在盒子里的盒子也可以装其他盒子,比如,大小为 $8$ 的盒子可以装下一个大小为 $4$ 的盒子且大小为 $4$ 的盒子事先已经装了一个大小为 $2$ 的盒子。 现在小 Y 想知道,最少能有多少个不被其他盒子装下的盒子? ## Input 第一行 $1$ 个正整数 $n$,表示盒子的数量。 第二行 $n$ 个正整数 $a_i$,表示每个盒子的大小,保证 $a_i$ 一定是 $2$ 的若干次方。 ## Output 一行一个正整数表示最少能有多少个不被其他盒子装下的盒子。 [samples] ## Background 搬运自 <http://czoj.com.cn/p/954>。数据为民间数据。 ## Note ### 样例 $\textbf 1$ 解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/uo8jxn0g.png) 图中盒子内部的灰色部分表示盒子不能用来装东西的一半容量,白色部分表示能用来装东西的一半容量,图中只有最大的盒子没有被装在其它盒子中,因此答案为 $1$。 ### 样例 $\textbf 2$ 解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/ygt207eh.png) ### 样例 $\textbf 3$ 解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/znl0c65g.png) ### 样例 $\textbf 4$ 解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/pis9wn32.png) ### 数据范围 参考数据:$2^{60}=1\ 152\ 921\ 504\ 606\ 846\ 976$。 对于所有数据,$1≤n≤10^5, 1≤a_i≤2^{60}$。 |测试点编号|特殊性质| |:-:|:-:| |$1\sim3$|$1\le n\le 3$| |$4\sim5$|$1\le a_i\le 4$| |$6\sim9$|$1\le n\le 1000$| |$10\sim12$|无|
Samples
Input #1
5
1 2 1 1 8
Output #1
1
Input #2
3
1 1 1
Output #2
3
Input #3
6
1 1 1 4 1 2
Output #3
3
Input #4
3
8 4 2
Output #4
1
API Response (JSON)
{
  "problem": {
    "name": "[常州市赛 2024] 盒子",
    "description": {
      "content": "小 Y 有 $n$ 个盒子,第 $i$ 个盒子的大小是 $a_i$,小 Y 保证 $a_i$ 一定是 $2$ 的若干次方,比如 $1,2,4,8,16,32,64,128,256,512,1024\\cdots$,一个大小为 $a_i$ 的盒子的容量是 $\\dfrac{a_i}2$,就是说它可以装下总大小不超过 $\\dfrac{a_i}2$ 的其他盒子,特别地,大小为 $1$ 的盒子不能装下其他盒子",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4228"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 Y 有 $n$ 个盒子,第 $i$ 个盒子的大小是 $a_i$,小 Y 保证 $a_i$ 一定是 $2$ 的若干次方,比如 $1,2,4,8,16,32,64,128,256,512,1024\\cdots$,一个大小为 $a_i$ 的盒子的容量是 $\\dfrac{a_i}2$,就是说它可以装下总大小不超过 $\\dfrac{a_i}2$ 的其他盒子,特别地,大小为 $1$ 的盒子不能装下其他盒子...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments