AT_abc353_b [ABC353B] AtCoder Amusement Park

题目描述

AtCoder 游乐园有一个可容纳 $K$ 人的游乐设施。现在，这个游乐设施的等待队列中有 $N$ 个团体排队。

从队首开始，第 $i$ 个团体（$1 \leq i \leq N$）有 $A_i$ 个人。对于所有的 $i$（$1 \leq i \leq N$），都有 $A_i \leq K$。

高桥君作为这个游乐设施的工作人员，将按照以下步骤引导排队的团体：

一开始，游乐设施中没有人被引导入内，空位有 $K$ 个。

1. 如果等待队列中没有团体，则启动游乐设施，并结束引导。
2. 比较游乐设施的空位数和等待队列队首团体的人数，执行以下两种情况之一：
   • 如果队首团体的人数大于游乐设施的空位数，则启动游乐设施。启动后，游乐设施的空位数恢复为 $K$。
   • 否则，将队首团体的所有人引导入游乐设施。队首团体从队列中移除，游乐设施的空位数减少该团体人数。
3. 返回步骤 1。

注意，引导开始后，不会有新的团体加入队列。在上述条件下，可以保证该流程在有限次操作后结束。

请你计算，从高桥君开始引导到引导结束，游乐设施一共被启动了多少次。

输入格式

输入以如下格式从标准输入给出。

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

7 6
2 5 1 4 1 2 3

输出 #1

4

输入输出样例 #2

输入 #2

7 10
1 10 1 10 1 10 1

输出 #2

7

输入输出样例 #3

输入 #3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

输出 #3

8

说明/提示

限制条件

• $1 \leq N \leq 100$
• $1 \leq K \leq 100$
• $1 \leq A_i \leq K\ (1 \leq i \leq N)$
• 所有输入均为整数

样例解释 1

一开始，$7$ 个团体按如下方式排队。

高桥君引导的部分过程如下图所示。

• 一开始，队首是 $2$ 人的团体，空位有 $6$ 个。因此，高桥君将队首团体引导入内，空位变为 $4$ 个。
• 接下来，队首是 $5$ 人的团体，人数多于空位 $4$，因此启动游乐设施。
• 空位恢复为 $6$，将队首团体引导入内，空位变为 $1$ 个。
• 接下来队首是 $1$ 人的团体，引导入内，空位变为 $0$ 个。

直到所有团体引导结束，高桥君一共启动了 $4$ 次游乐设施。因此，请输出 4。

由 ChatGPT 4.1 翻译