首页 > 试题广场 >

奶茶店特调

[编程题]奶茶店特调
  • 热度指数:16 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 512M,其他语言1024M
  • 算法知识视频讲解
在一家创意奶茶店,你是一位顶级的奶茶制作师。
顾客可以定制一杯独一无二的“千层特调”,这杯奶茶由多种口味的配料堆叠而成。
每种配料都有一个特定的风味编号。

你面前有一张初始配方单,详细记录了要依次添加的 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, \dots, I_{N-1},代表从下到上每一层配料的风味编号。
3. 第三行是一个整数 M,代表顾客提出的“升级”请求数量。
4. 第四行包含 M 个整数 U_0, U_1, \dots, U_{M-1},每个整数代表一个请求,内容是配料的**身份标识**(即它在初始配方单中的位置)。

数据范围 :
1 \le N \le 10^5
1 \le M \le 10^3
1 \le I_i \le 30
0 \le U_j < N


输出描述:
输出一个整数,代表所有操作完成后,奶茶中剩余的配料层数。
示例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

备注:
本题由牛友@Charles 整理上传

这道题你会答吗?花几分钟告诉大家答案吧!