题目描述
Problem Description
There are $n$ items, numbered from $1$ to $n$. The weight of the item numbered $i$ is denoted as $a_i$, which is a positive integer.
There is only one available box, and its maximum capacity is a positive integer $m$. Items are moved in batches, each batch moving a subset of the remaining items until all items are moved. The subset of items moved in each batch is chosen according to the following strategy:
Select the plan with the highest number of items whose total weight does not exceed $m$. If there are multiple plans with the highest number of items, choose the plan that results in the lexicographically largest sequence of item numbers when sorted in ascending order.
Calculate the number of batches required to move all items according to this strategy.
Input Format
The input consists of two lines. The first line contains two space-separated positive integers $n$ and $m$. The second line contains $n$ space-separated positive integers, representing the weights of the $n$ items $a_i$.
Output Format
Output a single positive integer, representing the number of batches required to complete the move.
Sample Input and Output
Sample Input #1
11 10
3 1 3 8 4 3 2 1 2 1 1
Sample Output #1
4
Sample Input #2
See the attached file 2.in.
Sample Output #2
See the attached file 2.ans.
Sample Input #3
See the attached file 3.in.
Sample Output #3
See the attached file 3.ans.
Notes/Hints
[Sample Explanation #1]
The first batch can move up to 6 items, with the sequence of item numbers being $6, 7, 8, 9, 10, 11$.
The second batch can move up to 3 items. There are 4 plans with the maximum number of items:
- Sequence $1, 2, 3$.
- Sequence $1, 2, 5$.
- Sequence $1, 3, 5$.
- Sequence $2, 3, 5$.
The lexicographically largest sequence is $2, 3, 5$.
The third batch can move 1 item, with the sequence being $4$.
The fourth batch can move 1 item, with the sequence being $1$.
[Subtasks]
| Subtask | Points | $n$ | $m$ |
|---|---|---|---|
| 1 | 5 | $n \leq 20$ | $m \leq 100$ |
| 2 | 25 | $n \leq 500$ | $m \leq 10^9$ |
| 3 | 20 | $n \leq 3000$ | $m \leq 10^9$ |
| 4 | 10 | $n \leq 50000$ | $m \leq 10$ |
| 5 | 40 | $n \leq 50000$ | $m \leq 10^9$ |
All data satisfies:
- $1 \leq n \leq 50000$, $1 \leq m \leq 10^9$;
- All item weights satisfy $1 \leq a_i \leq m, \ i=1 \dots n$.
[Hint]
For two sequences $a$ and $b$ of the same length that are not identical, the lexicographical order between $a$ and $b$ is defined as follows: find the first position $i$ where $a_i \neq b_i$, and if $a_i < b_i$ then $a < b$, otherwise if $a_i > b_i$ then $a > b$.
In this problem, $a$ and $b$ are sequences of item numbers involved in the moving plans, and the comparison between elements refers to the integer comparison between item numbers.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分