在一家创意奶茶店,你是一位顶级的奶茶制作师。 顾客可以定制一杯独一无二的“千层特调”,这杯奶茶由多种口味的配料堆叠而成。 每种配料都有一个特定的风味编号。 你面前有一张初始配方单,详细记录了要依次添加的 N 层配料的风味编号和它们的添加顺序(从 0 开始编号)。 这个初始的添加顺序将作为这层配料的身份标识。 例如,初始配方单为 `1 1 2 3 4`,则: 身份标识为 0 的配料,其风味编号是 1 。 身份标识为 1 的配料,其风味编号也是 1 。 身份标识为 2 的配料,其风味编号是 2 ,以此类推。 制作过程中,顾客可能会提出一些“升级”请求。每个请求会指定一个配料的身份标识。一旦收到请求,如果该身份标识对应的配料还存在于奶茶中,它就会进入“待升级”状态,并遵循以下规则进行融合: 1. 融合规则 1 :如果某“待升级”的配料层,其下方紧邻的配料层风味编号与它完全相同,那么这两层将融合成一层全新的配料。新配料的风味编号等于原风味编号加 1。 2. 融合规则 2 :新融合的配料层将继承“待升级”状态,并立即尝试与它下方新的相邻层继续融合,这个过程会不断重复,直到它下方没有相同风味的配料,或者它已成为奶茶的最底层。 3. 融合规则 3 :通过融合产生的新配料层是“隐藏款”,它没有身份标识。因此,顾客无法通过指令直接指定它进入“待升级”状态。但是,如果上方的配料层在融合后下沉,变为与它相邻,它依然可以作为被动方参与后续的融合。 完成所有顾客的“升级”请求后,你需要计算这杯“千层特调”最终还剩下多少层配料。
输入共 4 行: 1. 第一行是一个整数 N ,代表初始配方单上的配料层数。 2. 第二行包含 N 个整数 I_0, I_1, ..., I_N-1 ,代表从下到上每一层配料的风味编号。 3. 第三行是一个整数 M ,代表顾客提出的“升级”请求数量。 4. 第四行包含 M 个整数 U_0, U_1, ..., U_M-1 ,每个整数代表一个请求,内容是配料的**身份标识**(即它在初始配方单中的位置)。 数据范围 : 1 ≤ N ≤ 10^5 1 ≤ M ≤ 10^3 1 ≤ I_i ≤ 30 0 ≤ U_j < N
输出一个整数,代表所有操作完成后,奶茶中剩余的配料层数。
5 2 2 2 1 1 3 4 1 2
2
12 7 5 4 3 2 1 1 9 8 7 7 10 4 0 10 11 6
3
6 5 4 3 2 1 1 1 5
1
考点:模拟
数据规模 N ≤ 1e5 | 限制 3 秒 / 512MB | 标准输入输出
推荐方向:模拟
本题切入点
用双向链表按题意模拟融合:被指定的身份标识标记为「待升级」,反复检查其下方是否同风味,相同则合并成风味 +1 的新层并继承待升级状态(新层无身份标识,不可被直接指定)。
不涉及复杂算法,把题目描述的流程原样翻译成代码逐步执行即可。
思路框架(模拟 通法 · 非本题专属)
实现要点:结构上通常是一个外层循环包住若干 if/else 分支;只要状态定义清楚,正确率很高。
复杂度:时间 O(操作次数) | 空间 O(状态数)
该范式的通法易错点
对照本题
样例 1
5 / 2 2 2 1 1 / 3 / 4 1 22样例 2
12 / 7 5 4 3 2 1 1 9 8 7 7 10 / 4 / 0 10 11 63解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2025年秋招-华为-12月4号留学生开发岗。