21、大模型推理资源的最低成本分发
题目描述
当前只有若干个并发的大模型推理服务器，推理资源紧张，但是有 $N$ 个推理请求任务在申请推理服务中。每个推理服务都有一个优先级的分值，要求对每个推理请求任务分发推理资源。每个任务至少分配 1 千个 token 消耗的推理资源，相邻的两个任务，优先级高的那个任务会获得更多的 token 数（$X$ 千个 token 数）。请给每个推理请求任务分发 token，确保 $N$ 个请求任务消耗的 token 数最少（单位：千个 token）。
解答要求
时间限制：C/C++ 1000ms, 其他语言: 2000ms
内存限制：C/C++ 512MB, 其他语言: 1024MB
输入
输入是一个优先级的数组，数值越大，优先级越高。例如：1, 2, 3。
如果优先级小于等于 0 或者为空，该任务需要被放弃，不分配任务 token，且它的相邻任务不与该任务进行优先级比较。
比如：[1, -1, 2]的 token 总数是 2 千个。
输出
输出一个整数，代表 $N$ 个请求任务消耗的最少 token 总数。
（例如：输出6，代表分别给第一、二、三个任务分发 1 千、2 千、3 千个 token。）
样例 1
输入：
10, 10, 5输出：
4解释：分别给第一、二、三个任务分发 1 千、2 千、1 千个 token。
样例 2
输入：
4, 2, 6输出：
5解释：分别给第一、二、三个任务分发 2 千、1 千、2 千个 token。
根据你提供的题目描述和样例，这道题是一个典型的贪心算法问题，与经典的“分发糖果”（Candy Problem）非常相似。
题目核心逻辑分析
基础配额：每个有效任务（优先级 $> 0$）至少分配 $1$ 单位（$1000$ tokens）。
相邻比较：对于相邻的两个任务，如果其中一个优先级更高，它获得的 tokens 必须更多。
相等优先级：如果相邻任务优先级相等，题目并未强制要求它们获得相同数量，为了使总数最小，我们只需确保高优先级者更多，若相等则互不干扰。
特殊情况：优先级 $\le 0$ 或为空的任务被放弃（分配 $0$ tokens），且它们不参与相邻任务的优先级比较。这相当于将任务序列按放弃的任务为界，分割成了若干个独立的子序列。
算法设计：双向贪心扫描
为了严格遵守时间复杂度 $O(N)$ 和空间复杂度 $O(N)$，我们采用两次遍历的方法：
从左向右遍历：如果当前任务优先级高于左侧任务，则当前任务的 tokens 在左侧基础上 $+1$。
从右向左遍历：如果当前任务优先级高于右侧任务，则当前任务的 tokens 必须大于右侧。此时需取“当前值”与“右侧值 $+1$”的较大者，以同时满足左右两边的约束
import sys def solve(): # 从标准输入读取全部内容并去除首尾空白字符 try: input_data = sys.stdin.read().strip() except EOFError: return if not input_data: return # 预处理：去除输入中可能存在的方括号 [ ]，并按逗号分割 # 兼容 "10,10,5" 或 "[10,10,5]" 等格式 cleaned_str = input_data.replace('[', '').replace(']', '') if not cleaned_str: # 如果处理后为空（如输入是 "[]"），输出 0 print(0) return parts = cleaned_str.split(',') n = len(parts) priorities = [] # 1. 解析优先级并初始化 tokens 数组 # 优先级 <= 0 或为空的任务分配 0，其余初始分配 1 tokens = [0] * n for i in range(n): item = parts[i].strip() if not item: priorities.append(-1) # 视为空任务为已放弃 else: try: val = int(item) priorities.append(val) if val > 0: tokens[i] = 1 except ValueError: # 处理非数字字符串（如 null） priorities.append(-1) # 2. 前向遍历（左 -> 右）：确保比左邻居优先级高的任务拿更多 token for i in range(1, n): # 只有当相邻两任务都有效（>0）时才进行比较 if priorities[i] > 0 and priorities[i-1] > 0: if priorities[i] > priorities[i-1]: tokens[i] = tokens[i-1] + 1 # 3. 后向遍历（右 -> 左）：确保比右邻居优先级高的任务拿更多 token for i in range(n - 2, -1, -1): if priorities[i] > 0 and priorities[i+1] > 0: if priorities[i] > priorities[i+1]: # 取当前值与 (右侧+1) 的最大值，以同时满足左右约束 tokens[i] = max(tokens[i], tokens[i+1] + 1) # 输出最终的总 token 数（按题目单位：千个） print(sum(tokens)) if __name__ == '__main__': solve()
