【华为OD-E卷-最小调整顺序次数、特异性双端队列 100分（python、java、c++、js、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 要调整的最小次数。
用例
用例一：
输入：
5
head add 1
tail add 2
remove
head add 3
tail add 4
head add 5
remove
remove
remove
remove
输出：
1
python解法
- 解题思路：
- 任务目标：
处理一系列命令（add head, add tail, remove）对一个队列进行操作。
每次执行remove命令时，确保队列头部元素为指定的值current_remove，否则需要调整队列以满足条件。
统计所有remove命令中，为调整队列顺序而进行的排序操作次数。
实现逻辑：
使用一个列表模拟队列。
遍历命令：
对于add head和add tail命令，将元素插入队列的头部或尾部。
对于remove命令：
如果队列头部的元素与current_remove匹配，则直接移除。
否则，对队列进行排序，移除排序后的第一个元素，并记录一次调整操作。
最终返回调整次数。
def process_commands(cmds, n):# 队列初始化queue = []current_remove = 1 # 当前需要移除的目标值adjustments = 0 # 调整次数统计for cmd in cmds:# 处理当前命令handle_command(cmd, queue, current_remove)if cmd.startswith("remove"):# 对队列进行调整adjustments += adjust_queue(queue, current_remove)current_remove += 1 # 更新需要移除的目标值return adjustmentsdef handle_command(cmd, queue, current_remove):# 根据命令类型操作队列if "add" in cmd:_, _, x = cmd.split() # 提取要添加的值if "head" in cmd:queue.insert(0, int(x)) # 添加到队列头部else:queue.append(int(x)) # 添加到队列尾部def adjust_queue(queue, current_remove):# 检查队列头部是否为目标值if queue[0] == current_remove:queue.pop(0) # 如果匹配，直接移除头部return 0 # 无需调整，返回 0else:queue.sort() # 否则排序队列queue.pop(0) # 移除排序后的第一个元素return 1 # 记录一次调整操作# 输入获取
n = int(input()) # 命令对数
cmds = [input() for i in range(2 * n)] # 获取所有命令# 输出结果
print(process_commands(cmds, n))java解法
- 解题思路
- 任务目标：
处理一系列命令（head add、tail add、remove）对队列进行操作。
每次执行remove命令时，如果队列未排序（head add会导致队列无序），需要对队列进行排序，并统计排序次数。
最终输出所有remove命令中，因排序操作产生的调整次数。
核心逻辑：
使用一个变量queueSize记录队列的大小。
使用布尔变量sorted标记队列是否处于有序状态：
head add操作可能破坏有序状态，将sorted设为false。
如果在执行remove时队列无序，则需要排序（adjustments计数加1），并恢复有序状态。
遍历命令列表，依次处理队列的增删操作，并更新状态和调整计数。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int len = Integer.parseInt(in.nextLine()); // 读取命令对数int total = len * 2; // 总命令数为命令对数的两倍String[] cmds = new String[total];int j = 0;while (j < total) {cmds[j] = in.nextLine(); // 读取所有命令j++;}System.out.println(calculateAdjustments(cmds)); // 计算并输出调整次数}public static int calculateAdjustments(String[] cmds) {int queueSize = 0; // 当前队列的大小boolean sorted = true; // 标记队列是否处于有序状态int adjustments = 0; // 记录排序操作的次数int i = 0;while (i < cmds.length) {String cmd = cmds[i];if (cmd.startsWith("head add")) {// `head add` 操作可能破坏队列的有序状态if (queueSize > 0 && sorted) sorted = false;queueSize++; // 队列大小加1} else if (cmd.startsWith("tail add")) {// `tail add` 操作不会破坏队列的有序状态queueSize++; // 队列大小加1} else { // 处理 `remove` 操作if (queueSize == 0) { // 如果队列为空，跳过当前命令i++;continue;}if (!sorted) { // 如果队列无序，需要排序adjustments++; // 增加调整次数sorted = true; // 恢复有序状态}queueSize--; // 移除队列的一个元素}i++;}return adjustments; // 返回总调整次数}
}C++解法
- 解题思路
更新中
C解法
更新中
JS解法
处理一系列命令（head add、tail add、remove）操作一个堆栈。
如果命令是head add，可能导致堆栈的顺序被破坏，需要在执行remove命令时进行排序以恢复顺序。
统计排序操作的次数（即需要恢复顺序的操作次数）。
实现逻辑：
使用stackSize记录当前堆栈的大小。
使用needSort标记堆栈是否需要排序：
head add会导致无序，将needSort设为true。
tail add不会影响顺序。
在remove时，如果needSort为true，需要排序（增加排序计数并重置needSort）。
遍历命令数组，根据命令类型更新堆栈状态和排序计数。
输入输出：
输入：第一行为命令对数n，接下来是2 * n条命令。
输出：所有remove命令中因排序产生的调整次数。
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});let commands = [];
let numOps = 0;rl.on("line", (line) => {commands.push(line); // 读取输入if (commands.length === 1) {numOps = parseInt(commands[0]); // 第一行表示命令对数} else if (commands.length === 1 + 2 * numOps) {commands.shift(); // 移除第一行命令对数console.log(processCommands(commands)); // 处理命令并输出结果commands = [];}
});function processCommands(cmds) {let stackSize = 0; // 当前堆栈的大小let needSort = false; // 是否需要排序let operations = 0; // 排序操作次数统计cmds.forEach((cmd) => {if (cmd.startsWith("head add")) {// 如果是 `head add`，可能导致堆栈无序if (stackSize > 0) needSort = true; // 如果堆栈非空，标记需要排序stackSize++; // 增加堆栈大小} else if (cmd.startsWith("tail add")) {// 如果是 `tail add`，只增加堆栈大小，不影响顺序stackSize++;} else {// 如果是 `remove` 操作if (stackSize === 0) return; // 堆栈为空，跳过此命令if (needSort) {// 如果需要排序，增加排序操作计数operations++;needSort = false; // 排序完成后重置标记}stackSize--; // 减少堆栈大小}});return operations; // 返回总排序操作次数
}注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
