QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
Statistics

题目描述

有 $n$ 件物品,编号为 $1$ 到 $n$,编号为 $i$ 的物品重量记为 $a_i$,是一个正整数。

只有一个可用的箱子,它最大可容纳的重量是一个正整数 $m$。物品被分批搬运,每批搬走其中一部分,直至所有物品都被搬走。每个批次被搬走的物品是当时剩下物品的一个子集,按如下策略选择:

选择重量之和不超过 $m$ 且包含物品数量最多的方案,如果有多种数量最多的方案,则将被选择的物品编号从小到大排列成一个序列,选择使这个序列字典序最大的方案。

请计算出依此策略会分成多少批次来搬运。

输入格式

从标准输入读入数据。

输入共有两行,第一行包含两个空格分隔的正整数 $n, m$,第二行包含 $n$ 个空格隔开的正整数,依次为 $n$ 个物品的重量 $a_i$。

输出格式

输出到标准输出。

输出一个正整数,表示完成搬运所需的批次数。

样例1输入

11 10
3 1 3 8 4 3 2 1 2 1 1

样例1输出

4

样例1解释

第一次最多可以搬运 $6$ 件物品,编号序列为 $6, 7, 8, 9, 10, 11$。

第二次最多可以搬运 $3$ 件物品,这时有 $4$ 种数量最大的方案:

  • 编号序列 $1, 2, 3$。
  • 编号序列 $1, 2, 5$。
  • 编号序列 $1, 3, 5$。
  • 编号序列 $2, 3, 5$。

选择字典序最大的 $2, 3, 5$。

第三次最多可以搬运 $1$ 件物品,编号序列为 $4$。

第四次最多可以搬运 $1$ 件物品,编号序列为 $1$。

样例2

见题目目录下的 2.in2.ans

样例3

见题目目录下的 3.in3.ans

子任务

子任务分值$n$$m$
15$n \leq 20$$m \leq 100$
225$n \leq 500$$m \leq 10^9$
320$n \leq 3000$$m \leq 10^9$
410$n \leq 50000$$m \leq 10$
540$n \leq 50000$$m \leq 10^9$

全部数据满足:

  • $1 \leq n \leq 50000, 1 \leq m \leq 10^9$
  • 所有物品的重量满足 $1 \leq a_i \leq m, i=1 \dots n$

提示

对于两个等长且不相同的序列 $a$ 和 $b$,如果序列中的元素可以比较大小,那么 $a$ 与 $b$ 的字典序大小关系如下定义:从前向后找到第一个位置 $i$ 使 $a_i \neq b_i$,若 $a_i < b_i$ 则 $a < b$,否则 $a_i > b_i$ 时 $a>b$。

在本题中,$a$ 和 $b$ 是两个搬运方案中涉及的物品编号序列,元素之间的大小关系指的就是编号之间的整数比较。