{"problem":{"name":"[THUSC 2021] 搬东西","description":{"content":"有 $n$ 件物品，编号为 $1$ 到 $n$，编号为 $i$ 的物品重量记为 $a_i$，是一个正整数。 只有一个可用的箱子，它最大可容纳的重量是一个正整数 $m$。物品被分批搬运，每批搬走其中一部分，直至所有物品都被搬走。每个批次被搬走的物品是当时剩下物品的一个子集，按如下策略选择： 选择重量之和不超过 $m$ 且包含物品数量最多的方案，如果有多种数量最多的方案，则将被选择的物品编号从小到","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10240"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 件物品，编号为 $1$ 到 $n$，编号为 $i$ 的物品重量记为 $a_i$，是一个正整数。\n\n只有一个可用的箱子，它最大可容纳的重量是一个正整数 $m$。物品被分批搬运，每批搬走其中一部分，直至所有物品都被搬走。每个批次被搬走的物品是当时剩下物品的一个子集，按如下策略选择：\n\n选择重量之和不超过 $m$ 且包含物品数量最多的方案，如果有多种数量最多的方案，则将被选择的物品编号从小到大排列成一个序列，选择使这个序列字典序最大的方案。\n\n请计算出依此策略会分成多少批次来搬运。\n\n## Input\n\n输入共有两行，第一行包含两个空格分隔的正整数 $n, m$，第二行包含 $n$ 个空格隔开的正整数，依次为 $n$ 个物品的重量 $a_i$。\n\n## Output\n\n输出一个正整数，表示完成搬运所需的批次数。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n第一次最多可以搬运 $6$ 件物品，编号序列为 $6, 7, 8, 9, 10, 11$。\n\n第二次最多可以搬运 $3$ 件物品，这时有 $4$ 种数量最大的方案：\n\n+ 编号序列 $1, 2, 3$。\n+ 编号序列 $1, 2, 5$。\n+ 编号序列 $1, 3, 5$。\n+ 编号序列 $2, 3, 5$。\n\n选择字典序最大的 $2, 3, 5$。\n\n第三次最多可以搬运 $1$ 件物品，编号序列为 $4$。\n\n第四次最多可以搬运 $1$ 件物品，编号序列为 $1$。\n\n**【子任务】**\n\n|子任务|分值|$n$|$m$|\n|:----:|:----:|:----:|:----:|\n|$1$|$5$|$n \\leq 20$|$m \\leq 100$|\n|$2$|$25$|$n \\leq 500$|$m \\leq 10^9$|\n|$3$|$20$|$n \\leq 3000$|$m \\leq 10^9$|\n|$4$|$10$|$n \\leq 50000$|$m \\leq 10$|\n|$5$|$40$|$n \\leq 50000$|$m \\leq 10^9$|\n\n全部数据满足：\n\n+ $1 \\leq n \\leq 50000$，$1 \\leq m \\leq 10^9$；\n+ 所有物品的重量满足 $1 \\leq a_i \\leq m, \\ i=1 \\dots n$。\n\n**【提示】**\n\n对于两个等长且不相同的序列 $a$ 和 $b$，如果序列中的元素可以比较大小，那么 $a$ 与 $b$ 的字典序大小关系如下定义：从前向后找到第一个位置 $i$ 使 $a_i \\neq b_i$，若 $a_i < b_i$ 则 $a<b$，否则 $a_i>b_i$ 时 $a>b$。\n\n在本题中，$a$ 和 $b$ 是两个搬运方案中涉及的物品编号序列，元素之间的大小关系指的就是编号之间的整数比较。\n\n### 题目使用协议\n\n来自 清华大学 2021 年全国优秀中学生信息学体验营 (THUSC 2021)。\n\n以下『本仓库』皆指 THUSC 2021 官方仓库（[https://gitlink.org.cn/thusaa/thusc2021](https://gitlink.org.cn/thusaa/thusc2021)）\n\n1. 任何单位或个人都可以免费使用或转载本仓库的题目；\n2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；\n3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址。\n4. 清华大学计算机系保留一切权利。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10240","tags":["2021","O2优化","THUSC"],"sample_group":[["11 10\n3 1 3 8 4 3 2 1 2 1 1\n","4\n"],["见附件中的 2.in。","见附件中的 2.ans。"],["见附件中的 3.in。","见附件中的 3.ans。"]],"created_at":"2026-03-03 11:09:25"}}