OD刷题笔记合集🔗

最小的调整次数

问题描述

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

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"
                is_ok = (sz == 0);  // 如果队列为空，则新添加的数据就是正确的
            }
            sz++;  // 队列大小增加
        }
    }
    
    printf("%d\n", cnt);
    return 0;
}

• Javascript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n;
let lineCount = 0;
let is_ok = true;  // 表示当前队列头部是否是期望的数据
let sz = 0;        // 当前队列的大小
let cnt = 0;       // 需要调整的次数

rl.on('line', (line) => {
    if (lineCount === 0) {
        n = parseInt(line);
    } else {
        const op = line.split(' ');
        if (op[0] === 'remove') {
            sz--;  // 队列大小减少
            if (!is_ok) {
                cnt++;  // 如果之前需要调整，计数器加一
                is_ok = true;  // 重置状态
            }
        } else {
            if (op[0] === 'head') {
                is_ok = (sz === 0);  // 如果队列为空，则新添加的数据就是正确的
            }
            sz++;  // 队列大小增加
        }
    }
    lineCount++;
    
    if (lineCount === 2 * n + 1) {
        console.log(cnt);
        rl.close();
    }
});

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        scanner.nextLine();  // 消耗换行符
        
        boolean is_ok = true;  // 表示当前队列头部是否是期望的数据
        int sz = 0;            // 当前队列的大小
        int cnt = 0;           // 需要调整的次数
        
        for (int i = 0; i < 2 * n; i++) {
            String[] op = scanner.nextLine().split(" ");
            if (op[0].equals("remove")) {
                sz--;  // 队列大小减少
                if (!is_ok) {
                    cnt++;  // 如果之前需要调整，计数器加一
                    is_ok = true;  // 重置状态
                }
            } else {
                if (op[0].equals("head")) {
                    is_ok = (sz == 0);  // 如果队列为空，则新添加的数据就是正确的
                }
                sz++;  // 队列大小增加
            }
        }
        
        System.out.println(cnt);
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    bool is_ok = true;  // 表示当前队列头部是否是期望的数据
    int sz = 0;         // 当前队列的大小
    int cnt = 0;        // 需要调整的次数
    
    string op;
    for (int i = 0; i < 2 * n; i++) {
        cin >> op;
        if (op == "remove") {
            sz--;  // 队列大小减少
            if (!is_ok) {
                cnt++;  // 如果之前需要调整，计数器加一
                is_ok = true;  // 重置状态
            }
        } else {
            cin >> op >> op;  // 读取但忽略 "add" 和数字
            if (op[0] == 'h') {  // 'h' for "head"
                is_ok = (sz == 0);  // 如果队列为空，则新添加的数据就是正确的
            }
            sz++;  // 队列大小增加
        }
    }
    
    cout << cnt << "\n";
    return 0;
}