刷题笔记合集🔗

最小的调整次数

问题描述

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

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 (int i = 0; i < 2 * n; i++) {
        scanf("%s", op);
        if (strcmp(op, "remove") == 0) {
            sz--;  // 队列大小减少
            if (!is_ok) {
                cnt++;  // 如果之前需要调整，计数器加一
                is_ok = 1;  // 重置状态
            }
        } else {
            scanf("%*s %*d");  // 读取但忽略 "add" 和数字
            if (op[0] == 'h') {  // 'h' for "head"