题目内容

当前有若干台并发运行的大模型推理服务器，推理资源非常紧张。有 $N$ 个推理请求任务正在申请推理服务，每个任务带有一个优先级分值，分值越大表示优先级越高。资源以“千个 token”为单位进行分配。

对于每个任务，如果其优先级分值大于 0，则视为有效任务，至少需要分配 1 千个 token；如果优先级分值小于等于 0，该任务会被放弃，不分配任何 token，并且在相邻关系比较中忽略它。

对于相邻的两个有效任务，如果它们的优先级分值不同，那么优先级较高的任务必须获得比另一个任务更多的 token，至少多 1 千个 token；如果优先级分值相同，则没有额外的大小要求。

目标是在满足所有上述条件的前提下，使得 $N$ 个任务消耗的 token 总数最少。需要输出这个最少的 token 总数，单位为千个 token。

输入描述

输入共一行，包含若干个整数，由逗号分隔，代表优先级数组。

输出描述

输出一个整数，表示在所有满足条件的分配方案中，所有有效任务最少需要消耗的 token 总数，单位为千个 token。

样例1

输入

1,3,2

输出

4

说明

三个任务优先级分别为 1、3、2，均为有效任务，因此初始都至少分配 1 千 token。

第 2 个任务优先级 3 高于第 1 个任务优先级 1，所以第 2 个任务至少需要 $1+1=2$ 千 token。

第 2 个任务优先级 3 也高于第 3 个任务优先级 2，而第 3 个任务最少只需 1 千 token，因此第 2 个任务保持 2 千 token 即可满足比第 3 个任务多 1 的要求。

最终三个任务分别分配 1、2、1 千 token，总数为 $1+2+1=4$ 千 token。

样例2

输入

5,0,3

输出

2

说明

输入中有三个任务，优先级分别为 5、0、3。其中第 2 个任务优先级为 0，不大于 0，因此被放弃，不分配 token，并且在相邻比较中忽略它。

第 1 个任务和第 3 个任务都是有效任务，分别至少分配 1 千 token。由于第 2 个任务被忽略，这两个有效任务在原数组中不相邻，所以它们之间没有相邻比较约束。

因此最终 token 分配为 1、0、1，总数为 $1+0+1=2$ 千 token。

样例3

输入

7

输出

1

说明

输入只有一个任务，优先级为 7。因为 7 大于 0，该任务有效，至少需要分配 1 千 token。

不存在相邻任务，因此没有额外比较约束。最少 token 总数为 1。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写