题目描述

有一个特异性的双端队列，该队列可以从头部或尾部添加数据，但是只能从头部移出数据。

小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个数据；

1 ≤ n ≤ 3 * 10^5。

所有的数据均合法。

输出描述

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

测试样例1

输入：

5 head add 1 tail add 2 remove head add 3 tail add 4 head add 5 remove remove remove remove

输出：

1

解题思路

这个问题可以通过模拟双端队列的操作来解决。我们需要跟踪每个数字被添加到队列中的位置，以及它们被移除的顺序。由于题目要求移除数据的顺序为1到n，我们可以在添加数据时记录每个数字的位置，并在移除数据时检查是否需要调整。

Python代码解析

from collections import deque

def min_adjustments(n, operations):
    # 初始化双端队列和计数器
    queue = deque()
    count = 0
    positions = [0] * (n + 1)  # 记录每个数字的位置

    # 模拟操作
    for op in operations:
        if op.startswith("head add"):
            # 从头部添加数据
            value = int(op.split()[2])
            queue.appendleft(value)
            positions[value] = 'front'
        elif op.startswith("tail add"):
            # 从尾部添加数据
            value = int(op.split()[2])
            queue.append(value)
            positions[value] = 'back'
        elif op == "remove":
            # 移除数据
            if len(queue) > 0:
                value = queue.popleft()
                if positions[value] == 'back':
                    # 如果是从尾部添加的，需要调整
                    count += 1
                    # 将尾部添加的元素移动到头部
                    positions[value] = 'front'
                    queue.appendleft(value)

    # 返回最少调整次数
    return count


# 读取输入
n = int(input())
operations = []
for _ in range(2 * n):
    operations.append(input())

# 计算并输出结果
print(min_adjustments(n, operations))