#GYM104720B. Trinket Tidying Challenge
Trinket Tidying Challenge
Description
Chef Chomperio is passionate about organizing and tidying up trinkets. Currently, they have $N$ ($1 \leq N \leq 10^5$) trinkets to dispose of.
To efficiently manage the trinkets, Chef has trash bags with a limited capacity; each bag can accommodate a maximum of $K$ ($1 \leq K \leq 10^5$) pounds of trash. Each trinket has some weight between $1$ and $K$ pounds, and the Chef can only throw them away in the order they are presented.
Chef Chomperio wants to minimize the number of trash bags used while efficiently discarding all the trinkets. At all times, Chef can either continue filling the current bag if there is sufficient capacity or throw it away and start with a new bag, but cannot hold on to more than one partially filled bag.
Given the number of trinkets $N$ as well as the size of trash bags, $K$, help Chef Chomperio determine the minimum number of trash bags required to tidy the trinkets.
The first line contains two integers, $N$ $(1 \leq N \leq 10^5)$ and $K$ $(1 \leq K \leq 10^5)$, representing the number of unique trinkets to tidy up and the maximum capacity of a trash bag, respectively.
The second line contains $N$ integers separated by a single space, representing the sizes of the trinkets in the order Chef needs to discard them. The $i$-th integer is the weight of the $i$-th trinket $(1 \leq \text{{trinket weight}} \leq K)$.
Print a single integer, the minimum number of trash bags Chef Chomperio will use.
Input
The first line contains two integers, $N$ $(1 \leq N \leq 10^5)$ and $K$ $(1 \leq K \leq 10^5)$, representing the number of unique trinkets to tidy up and the maximum capacity of a trash bag, respectively.
The second line contains $N$ integers separated by a single space, representing the sizes of the trinkets in the order Chef needs to discard them. The $i$-th integer is the weight of the $i$-th trinket $(1 \leq \text{{trinket weight}} \leq K)$.
Output
Print a single integer, the minimum number of trash bags Chef Chomperio will use.
4 3
1 3 1 1
2 5
4 5
3
2
Note
In the first example, we bundle $(1)(3)(1, 1)$.
In the second example, we bundle $(4) (5)$.