4158： AtCoder Amusement Park

# AtCoder Amusement Park ### 内存 1024MB ### 时间 2S ## 题目描述 AtCoder游乐园有一个可以容纳$K$人的景点。现在，有$N$个团体排队等待这个景点。 从队伍前面数起的第$i$个团体$（1≤i≤N）$由$A_i$人组成。对于所有$i（1≤i≤N）$，都有$A_i≤K$。 小高作为这个景点的工作人员，将按照以下程序引导队伍中的团体： 初始时，没有人被引导到景点，有$K$个空座位。 1. 如果队伍中没有团体，启动景点并结束引导。 2. 比较景点中的空座位数与队伍前面团体的人数，执行以下操作之一： - 如果空座位数少于队伍前面团体的人数，启动景点。然后，空座位数再次变为$K$。 - 否则，引导队伍前面的整个团体进入景点。前面的团体从队伍中移除，空座位数减少该团体的人数。 3. 返回步骤1。 在这里，引导开始后不会有额外的团体加入队伍。在这些条件下，可以证明这个程序将在有限步骤内结束。 确定整个引导过程中景点将被启动多少次。 ## 输入格式 输入从标准输入中以下列格式给出： $N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$ ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例1 ``` 7 6 2 5 1 4 1 2 3 ``` ### 输出样例1 ``` 4 ``` ### 输入样例2 ``` 7 10 1 10 1 10 1 10 1 ``` ### 输出样例2 ``` 7 ``` ### 输入样例3 ``` 15 100 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 ``` ### 输出样例3 ``` 8 ``` ## 数据范围与提示 【样例1说明】 初始时，七个团体按以下顺序排队：  小高引导的部分过程如下图所示：  - 初始时，队伍前面的团体有2人，有6个空座位。因此，他引导前面的团体进入景点，剩下4个空座位。 - 接下来，队伍前面的团体有5人，超过了4个空座位，所以启动景点。 - 景点启动后，再次有6个空座位，所以引导前面的团体进入景点，剩下1个空座位。 - 接下来，队伍前面的团体有1人，所以他们被引导进入景点，剩下0个空座位。 总共，他在引导完成前启动景点四次。因此，输出4。  【数据范围】 $1 ≤ N,K ≤ 100, 1 ≤ A_i ≤ K （1 ≤ i ≤ N）$，所有输入值都是整数。 ## 题目来源 ABC353B