【最新华为OD机试E卷】最小的调整次数(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

② 最小的调整次数

问题描述

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

K小姐 依次执行 个指令往队列中添加数据和移出数据。其中 个指令是添加数据（可能从头部添加、也可能从尾部添加），依次添加 到 ； 个指令是移出数据。

现在要求移除数据的顺序为 。

为了满足最后输出的要求，K小姐 可以在任何时候调整队列中数据的顺序。

请问K小姐 最少需要调整几次才能够满足移除数据的顺序正好是 到 。

输入格式

第一行一个整数 ，表示数据的范围。

接下来的 行，其中有 行为添加数据，指令为：

• "head add x" 表示从头部添加数据
• "tail add x" 表示从尾部添加数据

另外 行为移出数据指令，指令为 "remove" 的形式，表示移出 个数据。

输出格式

输出一个整数，表示K小姐要调整的最小次数。

样例输入

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

样例输出

1

样例解释

无

数据范围

所有的数据均合法。

题解

贪心+结论题

这道题目的核心在于理解队列的特性和调整的必要性。

我们不用真的去模拟一个队列，因为每次都会 sort 一遍，只需要关注当前的队列是否有序即可

1. 队列的特性：可以从头部或尾部添加数据只能从头部移出数据我们需要按照 1 到 n 的顺序移出数据

2. 关键观察：当我们从头部添加数据时，这个数据会立即成为下一个被移出的数据当我们从尾部添加数据时，这个数据会在之前所有数据被移出后才能被移出

3. 调整的必要性：只有当队列头部的数据不是我们期望移出的数据时，才需要调整每次调整都会将正确的数据移到队列头部

4. 算法思路：用一个变量 is_ok 来表示当前队列头部是否是我们期望的数据当从头部添加数据时，如果队列为空，那么这个数据就是正确的；否则需要调整当从尾部添加数据时，不会影响当前队列头部的正确性当移出数据时，如果之前需要调整，那么计数器加一，并重置 is_ok 为 true

参考代码

• Python

# 读取输入的数据数量
n = int(input())

# 初始化变量
is_ok = True  # 表示当前队列头部是否是期望的数据
sz = 0  # 当前队列的大小
cnt = 0  # 需要调整的次数

# 处理 2n 个操作
for _ in range(2 * n):
    op = input().split()
    
    if op[0] == 'remove':
        sz -= 1  # 队列大小减少
        if not is_ok:
            cnt += 1  # 如果之前需要调整，计数器加一
            is_ok = True  # 重置状态
    else:
        if op[0] == 'head':
            is_ok = (sz == 0)  # 如果队列为空，则新添加的数据就是正确的
        sz += 1  # 队列大小增加

# 输出结果
print(cnt)

• C

#include <stdio.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);
    
    int is_ok = 1;  // 表示当前队列头部是否是期望的数据
    int sz = 0;     // 当前队列的大小
    int cnt = 0;    // 需要调整的次数
    
    char op[110];
    for