作业限放接单

题目内容

云计算里一条 CI/CD 流水线由若干作业排成队列，用数组 $arr$ 表示，格子里的值是该作业耗时。

资源不够，不能把队列里每一项都跑完，约定如下：

1. 从队列最左侧开始依次审阅
2. 对当前作业，可以选择跑掉或者放掉
3. 选择跑掉时，把对应耗时累加进去
4. 选择放掉时，不加耗时，并继续看后面的作业
5. 硬性限制：连续被放掉的作业个数不能大于 $lim$
6. 目标：在上述限制下刚好跑完 $t$ 个作业，且累加耗时尽可能小

输入描述

• $arr$: 作业耗时数组，格子里的值是该项耗时
• $t$: int - 必须刚好跑完的作业个数
• $lim$: int - 连续放掉的最大个数

参数约束：

• $0 \le arr.length \le 1000$
• $1 \le arr_i \le 10000$
• $0 \le t \le arr.length$
• $0 \le lim \le 1000$

输出描述

int - 最小累加耗时；队列为空（$arr.length==0$）时输出 $0$；若无法刚好跑完 $t$ 个作业，返回 $-1$

样例1

输入

9 8 7 6 11 12 10
2
1

输出

-1

说明 队列长 $7$，要刚好跑 $2$ 项，$lim=1$。即使尽量分散放掉，连续放掉上限也撑不住剩下的 $5$ 项，因此给出 $-1$。

样例2

输入

11 4 15 6 8
4
3

输出

29

说明 一种跑法：跑 $11$、$4$，放掉 $15$，再跑 $6$ 与 $8$。

• 刚好跑了 $4$ 项（$11,4,6,8$）
• 累加耗时 $= 11+4+6+8=29$
• 各段连续放掉长度均不超过 $3$

其余合法跑法都至少要带上 $15$，耗时更大，因此答案是 $29$。

样例3

输入

4 80 4 80 4 80 4
4
2

输出

16

说明 跑第 $1$、$3$、$5$、$7$ 项，三处 $80$ 各自单独放掉。

• 刚好跑了 $4$ 项
• 累加耗时 $= 4+4+4+4=16$
• 连续放掉长度均为 $1$（$\le 2$）

把任何一项 $80$ 跑进来都会让耗时变大，故最小值是 $16$。

样例4

输入

0
4

输出

0

说明 队列里没有任何作业，按约定给出 $0$。