题目概述

本题涉及一个特异性的双端队列（deque），该队列支持以下操作：

• 添加操作：

  • head add x：从队列头部添加元素 x。
  • tail add x：从队列尾部添加元素 x。

• 移出操作：

  • remove：从队列头部移出一个元素。

小A将依次执行 2n 个指令，其中包含 n 个添加操作和 n 个移出操作。添加操作依次添加数字 1 到 n，添加的位置可以选择头部或尾部。所有移出操作必须按照 1 到 n 的顺序依次移出。

为了满足移出顺序的要求，小A可以在任何时候对队列中的元素顺序进行调整。题目要求求出小A 最少需要进行多少次调整，才能确保移出的顺序严格为 1 到 n。

思路:

因为本题的数据插入均是按照$1-n$的顺序所以只需考虑队列是否为空和是头插还是尾插即可,如果为空,那么$remove$直接跳过,记录$idx$为队列大小直接++即可,尾插显然不影响顺序,头插的时候判断是否为空,为空不影响,不为空那么此时如果是排序状态就会转变为乱序状态,此时如果$remove$就需要答案++

题解思路

题目给定一系列操作，这些操作分为三种：

1. 头插入（h），即将一个元素插入队列的头部。
2. 尾插入（t），即将一个元素插入队列的尾部。
3. 删除操作（remove），即从队列中移除一个元素。

由于操作是按照 $1-n$ 的顺序进行的，我们只需考虑当前队列是否为空、是否为头插入操作以及队列的有序状态。

状态记录

• mk：用于记录队列当前是否处于有序状态。初始设为 1（有序）。
• idx：用于记录队列中当前元素的数量。
• res：用于记录在删除操作时状态变化的次数。

操作流程

1. 头插入（h）：

   • 如果队列不为空且当前状态为有序，将状态标记为无序（mk=0）。
   • 增加队列大小计数（idx++）。

2. 尾插入（t）：

   • 直接增加队列大小计数（idx++），不影响状态。

3. 删除操作：

   • 如果队列为空，跳过此操作。
   • 如果队列不为空且当前状态为无序，则增加状态变化计数（res++）。
   • 减少队列大小计数（idx--）。

c++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;  // 输入操作的总数量（插入和删除的总次数）
    cin >> n;

    bool mk = 1; // 记录当前队列是否处于有序状态，1表示有序，0表示无序
    int idx = 0; // 记录队列中当前的元素数量
    int res = 0; // 记录状态变化次数
    cin.ignore();
    // 总共进行 n*2 次操作
    for (int i = 1; i <= n * 2; i++) {
        string s; // 用于存储每次的操作
        getline(cin, s); // 读取整行输入
        
        if (s[0] == 'h') { // 处理头插入操作
            if (idx > 0 && mk) // 如果队列不为空并且当前有序
                mk = 0; // 则状态变为无序
            idx++; // 队列元素数量增加
        } 
        else if (s[0] == 't') { // 处理尾插入操作
            idx++; // 队列元素数量增加
        } 
        else { // 处理删除操作
            if (idx == 0) // 如果队列为空，跳过操作
                continue;
            if (!mk) { // 如果当前状态为无序
                res++; // 增加状态变化计数
                mk = 1; // 状态标记为有序（因为删除了一个元素）
            }
            idx--; // 队列元素数量减少
        }
    }
    cout << res << endl; // 输出状态变化的次数
}

python

def main():
    n = int(input())  # 输入操作的总数量（插入和删除的总次数）
    
    mk = True  # 记录当前队列是否处于有序状态，True表示有序，False表示无序
    idx = 0  # 记录队列中当前的元素数量
    res = 0  # 记录状态变化次数
    
    # 总共进行 n*2 次操作
    for i in range(n * 2):
        s = input().strip()  # 读取整行输入
        
        if s[0] == 'h':  # 处理头插入操作
            if idx > 0 and mk:  # 如果队列不为空并且当前有序
                mk = False  # 则状态变为无序
            idx += 1  # 队列元素数量增加
        elif s[0] == 't':  # 处理尾插入操作
            idx += 1  # 队列元素数量增加
        else:  # 处理删除操作
            if idx == 0:  # 如果队列为空，跳过操作
                continue
            if not mk:  # 如果当前状态为无序
                res += 1  # 增加状态变化计数
                mk = True  # 状态标记为有序（因为删除了一个元素）
            idx -= 1  # 队列元素数量减少
    
    print(res)  # 输出状态变化的次数

if __name__ == "__main__":
    main()

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 输入操作的总数量（插入和删除的总次数）

        boolean mk = true;  // 记录当前队列是否处于有序状态，true表示有序，false表示无序
        int idx = 0;  // 记录队列中当前的元素数量
        int res = 0;  // 记录状态变化次数
        scanner.nextLine();  // 处理换行符

        // 总共进行 n*2 次操作
        for (int i = 1; i <= n * 2; i++) {
            String s = scanner.nextLine().trim();  // 读取整行输入并去掉多余空白字符

            if (s.startsWith("h")) {  // 处理头插入操作
                if (idx > 0 && mk) {  // 如果队列不为空并且当前有序
                    mk = false;  // 则状态变为无序
                }
                idx++;  // 队列元素数量增加
            } else if (s.startsWith("t")) {  // 处理尾插入操作
                idx++;  // 队列元素数量增加
            } else {  // 处理删除操作
                if (idx == 0)  // 如果队列为空，跳过操作
                    continue;
                if (!mk) {  // 如果当前状态为无序
                    res++;  // 增加状态变化计数
                    mk = true;  // 状态标记为有序（因为删除了一个元素）
                }
                idx--;  // 队列元素数量减少
            }
        }
        System.out.println(res);  // 输出状态变化的次数
    }
}

题目内容

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

小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步：[1]

第2步：[1,2]

第3步：头部删除1，无需调整，还剩[2]

第4步：[3,2]

第5步：[3,2,4]

第6步：[5,3,2,4]

第7步：调整顺序为[2，3，4，5]，再删除头部2，还剩[3，4，5]

第8步：头部删除3，无需调整，还剩[4，5]

第9步：头部删除4，无需调整，还剩[5]

第10步：头部删除5，无需调整

只需要调整1次