页面加载中…
AI007. Prefix Cache 调度器
困难通过率 0% · 提交 0 · 通过 0
算法机考高频题型改编 · 聚焦「算法」 · 难度：困难
推理服务维护 S 个 Prefix Cache 槽位，每个槽位保存一段 token 序列和当前负载。每来一个请求，需要选择一个槽位复用最长公共前缀；如果多个槽位的公共前缀长度相同，选择当前负载更小的槽位；仍并列则选择编号更小的槽位。请求处理后，该槽位的负载增加未命中的 token 数，并将缓存序列更新为本次请求序列。
这类题属于算法机考高频题型中「算法」方向的高频题型，通常考察对「算法」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
输入描述
第一行输入 S Q。接下来 S 行，每行输入 load len 和 len 个 token，表示一个缓存槽位。随后 Q 行，每行输入 len 和 len 个 token，表示一个请求。
输出描述
输出 Q 行。每行包含选择的槽位编号和复用的前缀长度。槽位编号从 1 开始。
示例
示例 1
输入示例
3 2 3 3 1 2 3 1 3 1 2 4 0 1 9 3 1 2 5 2 9 8
输出示例
2 2 3 1
说明：
选择最长公共前缀
示例 2
输入示例
2 1 5 3 4 5 6 2 2 4 5 3 4 5 6
输出示例
1 3
说明：
完全命中缓存
时间限制 3000 ms · 内存限制 256 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
本题暂无题解精讲。
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
