华为OD统一考试 - 执行时长

题目描述

为了充分发挥GPU算力，需要尽可能多的将任务交给GPU执行，现在有一个任务数组，数组元素表示在这1秒内新增的任务个数且每秒都有新增任务。

假设GPU最多一次执行n个任务，一次执行耗时1秒，在保证GPU不空闲情况下，最少需要多长时间执行完成。

输入描述

• 第一个参数为GPU一次最多执行的任务个数，取值范围[1, 10000]
• 第二个参数为任务数组长度，取值范围[1, 10000]
• 第三个参数为任务数组，数字范围[1, 10000]

输出描述

• 执行完所有任务最少需要多少秒。

用例

题目解析

题干中有一个段话很关键："数组元素表示在这1秒内新增的任务个数且每秒都有新增任务"，也就是说，数组中的任务个数不是一次性push完的，而是每过1s才push一次，而这刚好和GPU单次执行时间1s相温吻合。

比如

4

5

5 4 1 1 1

第1s时，任务数组中只有一个元素5，

然后GPU开始将这5个任务接收处理，但是1s时间，GPU只能处理4个，因此第1s结束后，还剩余1个任务没处理完。

第2s时，任务数组又加入一个元素4，

然后GPU将新增的4个任务接收处理，但是上一次还遗留1个任务没处理完，而GPU在1s内只能处理4个任务，因此本轮会遗留1个任务

第3s时，任务数组又加入一个元素1，

然后GPU将新增的1个任务接收处理，，但是上一次还遗留1个任务没处理完，而GPU在1s内只能处理4个任务，因此本轮不会遗留任务。

第4s时，任务数组又加入一个元素1，

由于没有遗留任务，且GPU在1s可以处理4个，因此本轮不会遗留任务

第5s时，任务数组又加入一个元素1，

由于没有遗留任务，且GPU在1s可以处理4个，因此本轮不会遗留任务

因此GPU需要花费5s来处理完所有任务。

同理可得

3

5

1 2 3 4 5

需要花费6s来处理所有任务。

但是这种逻辑似乎和题目要求得 “在保证GPU不空闲情况下，最少需要多长时间执行完成”

比如用例1中，

• 第1s只有1个任务需要处理，但是GPU最多可以处理3个，因此会发生GPU空闲
• 第2s只