(新卷,100分) - 最小的调整次数特异性双端队列（Java Python JS C++ C ）

题目描述

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

小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

说明

解题思路

Java

import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int number = scanner.nextInt();//数据的范围 scanner.nextLine(); Queue<Integer> queue = new LinkedList<>();//模拟双端队列 boolean in_order = true;//是否按顺序删除 int result = 0;//最小的调整顺序次数 for (int i = 0; i < 2 * number; i++) { String input_str = scanner.nextLine(); String[] operation = input_str.split(" "); if (operation[0].equals("head")) {//从头部添加元素 if (!queue.isEmpty() && in_order) {//不按顺序删除 in_order = false; } queue.add(Integer.parseInt(operation[2])); } else if (operation[0].equals("tail")) {//从尾部添加元素 queue.add(Integer.parseInt(operation[2])); } else {//删除元素 if (queue.isEmpty()) { continue; } if (!in_order) {//不按顺序删除 result++; in_order = true; } queue.poll(); } } System.out.println(result);//输出最小的调整顺序次数 } }

Python

from collections import deque number = int(input()) # 数据的范围 queue = deque() # 模拟双端队列 in_order = True # 是否按顺序删除 result = 0 # 最小的调整顺序次数 for i in range(2 * number): input_str = input() operation = input_str.split(" ") if operation[0] == "head": # 从头部添加元素 if len(queue) != 0 and in_order: # 不按顺序删除 in_order = False queue.appendleft(int(operation[2])) elif operation[0] == "tail": # 从尾部添加元素 queue.append(int(operation[2])) else: # 删除元素 if len(queue) == 0: continue if not in_order: # 不按顺序删除 result += 1 in_order = True queue.pop() print(result) # 输出最小的调整顺序次数

JavaScript

const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let number = 0; let operations = []; rl.on('line', (input) => { if (number === 0) { number = parseInt(input); } else { operations.push(input.split(" ")); if (operations.length === 2 * number) { rl.close(); } } }); const queue = []; // 模拟双端队列 let in_order = true; // 是否按顺序删除 let result = 0; // 最小的调整顺序次数 rl.on('close', () => { for (let i = 0; i < 2 * number; i++) { const operation = operations[i]; if (operation[0] === "head") { // 从头部添加元素 if (queue.length !== 0 && in_order) { // 不按顺序删除 in_order = false; } queue.unshift(parseInt(operation[2])); } else if (operation[0] === "tail") { // 从尾部添加元素 queue.push(parseInt(operation[2])); } else { // 删除元素 if (queue.length === 0) { continue; } if (!in_order) { // 不按顺序删除 result += 1; in_order = true; } queue.pop(); } } console.log(result); // 输出最小的调整顺序次数 });

C++

#include <iostream> #include <queue> using namespace std; int main() { int number; cin >> number; cin.ignore(); queue<int> queue; bool in_order = true; int result = 0; for (int i = 0; i < 2 * number; i++) { string input_str; getline(cin, input_str); string operation[3]; int j = 0; for (char c : input_str) { if (c == ' ') { j++; } else { operation[j] += c; } } if (operation[0] == "head") { if (!queue.empty() && in_order) { in_order = false; } queue.push(stoi(operation[2])); } else if (operation[0] == "tail") { queue.push(stoi(operation[2])); } else { if (queue.empty()) { continue; } if (!in_order) { result++; in_order = true; } queue.pop(); } } cout << result << endl; return 0; }

C语言

#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 600000 // 定义队列的最大容量（2n） int queue[MAX_SIZE]; // 模拟双端队列的数组 int front = 0; // 队列头部索引 int rear = -1; // 队列尾部索引 int size = 0; // 当前队列中的元素数量 int main() { int n; scanf("%d", &n); // 读取数据范围n int result = 0; // 记录最小的调整顺序次数 int expected = 1; // 期望移除的下一个元素 int in_order = 1; // 标记是否按顺序删除 for (int i = 0; i < 2 * n; i++) { char operation[10]; int x; scanf("%s", operation); // 读取操作类型 if (operation[0] == 'r') { // 如果是 "remove" 操作 if (queue[front] != expected) { // 如果移除的元素不是期望的 in_order = 0; // 标记为不按顺序 } else { expected++; // 移除的元素符合预期，更新下一个期望值 } front = (front + 1) % MAX_SIZE; // 更新头部索引 size--; // 减少队列中的元素数量 } else { // 如果是 "head add" 或 "tail add" 操作 scanf("%*s %d", &x); // 读取要添加的元素x if (operation[0] == 'h') { // 如果是 "head add" front = (front - 1 + MAX_SIZE) % MAX_SIZE; // 更新头部索引 queue[front] = x; // 从头部添加元素 } else { // 如果是 "tail add" rear = (rear + 1) % MAX_SIZE; // 更新尾部索引 queue[rear] = x; // 从尾部添加元素 } size++; // 增加队列中的元素数量 } if (!in_order && size == 0) { // 如果当前不按顺序且队列为空 result++; // 增加调整次数 in_order = 1; // 重置为按顺序状态 } } printf("%d\n", result); // 输出最小的调整顺序次数 return 0; }