华为 · 模拟 · 算法编程题
华为 模拟 N ≤ 1e5 时限 3 秒 / 512 MB

题目描述

在一家创意奶茶店,你是一位顶级的奶茶制作师。
顾客可以定制一杯独一无二的“千层特调”,这杯奶茶由多种口味的配料堆叠而成。
每种配料都有一个特定的风味编号。
你面前有一张初始配方单,详细记录了要依次添加的 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
输出描述
输出一个整数,代表所有操作完成后,奶茶中剩余的配料层数。

样例共 3 组

样例 1
输入
5
2 2 2 1 1
3
4 1 2
输出
2
样例 2
输入
12
7 5 4 3 2 1 1 9 8 7 7 10
4
0 10 11 6
输出
3
样例 3
输入
6
5 4 3 2 1 1
1
5
输出
1

算法解析依据充分

考点:模拟

数据规模 N ≤ 1e5 | 限制 3 秒 / 512MB | 标准输入输出

题目画像

  • 数据规模:N ≤ 1e5,M ≤ 1e3
  • 元素值域:I_i ≤ 30(注意整数类型选择,避免溢出)
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:3 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:模拟

本题切入点

用双向链表按题意模拟融合:被指定的身份标识标记为「待升级」,反复检查其下方是否同风味,相同则合并成风味 +1 的新层并继承待升级状态(新层无身份标识,不可被直接指定)。

不涉及复杂算法,把题目描述的流程原样翻译成代码逐步执行即可。

思路框架(模拟 通法 · 非本题专属)

  1. 用变量记录题目要求的「状态」(当前值、剩余数量、当前位置等)。
  2. 按题面给出的顺序,把每一步操作写成一段代码,逐条执行。
  3. 每一步执行后更新状态,并在题目要求的位置输出或累计答案。
  4. 注意循环的边界:执行多少次、何时终止、是否能终止。

实现要点:结构上通常是一个外层循环包住若干 if/else 分支;只要状态定义清楚,正确率很高。

复杂度:时间 O(操作次数) | 空间 O(状态数)

该范式的通法易错点

  • 终止条件写错导致死循环或漏做最后一次操作。
  • 状态更新顺序颠倒(先改了下标又用旧下标)。
  • 题目里「最多 / 恰好 / 至少」的语义差别没区分。

对照本题

  • 数据规模 N ≤ 1e5,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 元素值域最大到 30 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入:5 / 2 2 2 1 1 / 3 / 4 1 2
  • 输出:2

样例 2

  • 输入:12 / 7 5 4 3 2 1 1 9 8 7 7 10 / 4 / 0 10 11 6
  • 输出:3

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2025年秋招-华为-12月4号留学生开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解