E卷-(100分)最小的调整次数
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 到 n 的顺序移出数据
-
关键观察:当我们从头部添加数据时,这个数据会立即成为下一个被移出的数据当我们从尾部添加数据时,这个数据会在之前所有数据被移出后才能被移出
-
调整的必要性:只有当队列头部的数据不是我们期望移出的数据时,才需要调整每次调整都会将正确的数据移到队列头部
-
算法思路:用一个变量
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;
}
#OD##机考##笔试#本专栏收集并整理了一些刷题笔记