{"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$ 的盒子不能装下其他盒子。并且，装在盒子里的盒子也可以装其他盒子，比如，大小为 $8$ 的盒子可以装下一个大小为 $4$ 的盒子且大小为 $4$ 的盒子事先已经装了一个大小为 $2$ 的盒子。\n\n现在小 Y 想知道，最少能有多少个不被其他盒子装下的盒子？\n\n## Input\n\n第一行 $1$ 个正整数 $n$，表示盒子的数量。\n\n第二行 $n$ 个正整数 $a_i$，表示每个盒子的大小，保证 $a_i$ 一定是 $2$ 的若干次方。\n\n## Output\n\n一行一个正整数表示最少能有多少个不被其他盒子装下的盒子。\n\n[samples]\n\n## Background\n\n搬运自 <http://czoj.com.cn/p/954>。数据为民间数据。\n\n## Note\n\n### 样例 $\\textbf 1$ 解释\n![](https://cdn.luogu.com.cn/upload/image_hosting/uo8jxn0g.png)\n图中盒子内部的灰色部分表示盒子不能用来装东西的一半容量，白色部分表示能用来装东西的一半容量，图中只有最大的盒子没有被装在其它盒子中，因此答案为 $1$。\n### 样例 $\\textbf 2$ 解释\n![](https://cdn.luogu.com.cn/upload/image_hosting/ygt207eh.png)\n### 样例 $\\textbf 3$ 解释\n![](https://cdn.luogu.com.cn/upload/image_hosting/znl0c65g.png)\n### 样例 $\\textbf 4$ 解释\n![](https://cdn.luogu.com.cn/upload/image_hosting/pis9wn32.png)\n### 数据范围\n参考数据：$2^{60}=1\\ 152\\ 921\\ 504\\ 606\\ 846\\ 976$。\n\n对于所有数据，$1≤n≤10^5, 1≤a_i≤2^{60}$。\n\n|测试点编号|特殊性质|\n|:-:|:-:|\n|$1\\sim3$|$1\\le n\\le 3$|\n|$4\\sim5$|$1\\le a_i\\le 4$|\n|$6\\sim9$|$1\\le n\\le 1000$|\n|$10\\sim12$|无|","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4228","tags":["贪心","2024","江苏","排序","双指针 two-pointer","科创活动","小学活动"],"sample_group":[["5\n1 2 1 1 8","1"],["3\n1 1 1","3"],["6\n1 1 1 4 1 2","3"],["3\n8 4 2","1"]],"created_at":"2026-03-03 11:09:25"}}