华为OD机试题 特异性双端队列 or 最小调整顺序次数

2023-04-21 17:41:16 浏览数 (1)

本期题目:特异性双端队列 or 最小调整顺序次数

题目

有一个特异性的双端队列,该队列可以从头部到尾部添加数据,但是只能从头部移除数据。 小 A 一次执行 2n 个指令往队列中添加数据和移除数据, 其中 n 个指令是添加数据(可能从头部也可以从尾部添加) 依次添加 1 到 n , n 个指令是移出数据 现在要求移除数据的顺序为 1 到 n , 为了满足最后输出的要求, 小 A 可以在任何时候调整队列中的数据的顺序 请问,小 A 最少需要调整几次才能满足移除数据的顺序正好是 1 到 n

输入

第一行一个整数 n ,表示数据范围 接下来有 2n 行,其中有 n 行为添加数据: 指令head add x表示从头部添加数据x tail add x表示从尾部添加数据x 另外 n 行为移除数据指令,指令为remove形式,表示移除一个数据 1≤n≤3×10^5105

输出

一个整数,表示小 A 要调整的最小次数

0 人点赞