#P3079. 最小的调整次数(100分)
-
1000ms
Tried: 169
Accepted: 44
Difficulty: 3
所属公司 :
华为od
最小的调整次数(100分)
题目概述
本题涉及一个特异性的双端队列(deque),该队列支持以下操作:
-
添加操作:
head add x:从队列头部添加元素x。tail add x:从队列尾部添加元素x。
-
移出操作:
remove:从队列头部移出一个元素。
小A将依次执行 2n 个指令,其中包含 n 个添加操作和 n 个移出操作。添加操作依次添加数字 1 到 n,添加的位置可以选择头部或尾部。所有移出操作必须按照 1 到 n 的顺序依次移出。
为了满足移出顺序的要求,小A可以在任何时候对队列中的元素顺序进行调整。题目要求求出小A 最少需要进行多少次调整,才能确保移出的顺序严格为 1 到 n。
思路:
因为本题的数据插入均是按照1−n的顺序所以只需考虑队列是否为空和是头插还是尾插即可,如果为空,那么remove直接跳过,记录idx为队列大小直接++即可,尾插显然不影响顺序,头插的时候判断是否为空,为空不影响,不为空那么此时如果是排序状态就会转变为乱序状态,此时如果remove就需要答案++
题解思路
题目给定一系列操作,这些操作分为三种:
- 头插入(h),即将一个元素插入队列的头部。
- 尾插入(t),即将一个元素插入队列的尾部。
- 删除操作(remove),即从队列中移除一个元素。
由于操作是按照 1−n 的顺序进行的,我们只需考虑当前队列是否为空、是否为头插入操作以及队列的有序状态。
状态记录
mk:用于记录队列当前是否处于有序状态。初始设为1(有序)。idx:用于记录队列中当前元素的数量。res:用于记录在删除操作时状态变化的次数。
操作流程
-
头插入(h):
- 如果队列不为空且当前状态为有序,将状态标记为无序(
mk=0)。 - 增加队列大小计数(
idx++)。
- 如果队列不为空且当前状态为有序,将状态标记为无序(
-
尾插入(t):
- 直接增加队列大小计数(
idx++),不影响状态。
- 直接增加队列大小计数(
-
删除操作:
- 如果队列为空,跳过此操作。
- 如果队列不为空且当前状态为无序,则增加状态变化计数(
res++)。 - 减少队列大小计数(
idx--)。
c++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; // 输入操作的总数量(插入和删除的总次数)
cin >> n;
bool mk = 1; // 记录当前队列是否处于有序状态,1表示有序,0表示无序
int idx = 0; // 记录队列中当前的元素数量
int res = 0; // 记录状态变化次数
cin.ignore();
// 总共进行 n*2 次操作
for (int i = 1; i <= n * 2; i++) {
string s; // 用于存储每次的操作
getline(cin, s); // 读取整行输入
if (s[0] == 'h') { // 处理头插入操作
if (idx > 0 && mk) // 如果队列不为空并且当前有序
mk = 0; // 则状态变为无序
idx++; // 队列元素数量增加
}
else if (s[0] == 't') { // 处理尾插入操作
idx++; // 队列元素数量增加
}
else { // 处理删除操作
if (idx == 0) // 如果队列为空,跳过操作
continue;
if (!mk) { // 如果当前状态为无序
res++; // 增加状态变化计数
mk = 1; // 状态标记为有序(因为删除了一个元素)
}
idx--; // 队列元素数量减少
}
}
cout << res << endl; // 输出状态变化的次数
}
python
def main():
n = int(input()) # 输入操作的总数量(插入和删除的总次数)
mk = True # 记录当前队列是否处于有序状态,True表示有序,False表示无序
idx = 0 # 记录队列中当前的元素数量
res = 0 # 记录状态变化次数
# 总共进行 n*2 次操作
for i in range(n * 2):
s = input().strip() # 读取整行输入
if s[0] == 'h': # 处理头插入操作
if idx > 0 and mk: # 如果队列不为空并且当前有序
mk = False # 则状态变为无序
idx += 1 # 队列元素数量增加
elif s[0] == 't': # 处理尾插入操作
idx += 1 # 队列元素数量增加
else: # 处理删除操作
if idx == 0: # 如果队列为空,跳过操作
continue
if not mk: # 如果当前状态为无序
res += 1 # 增加状态变化计数
mk = True # 状态标记为有序(因为删除了一个元素)
idx -= 1 # 队列元素数量减少
print(res) # 输出状态变化的次数
if __name__ == "__main__":
main()
java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 输入操作的总数量(插入和删除的总次数)
boolean mk = true; // 记录当前队列是否处于有序状态,true表示有序,false表示无序
int idx = 0; // 记录队列中当前的元素数量
int res = 0; // 记录状态变化次数
scanner.nextLine(); // 处理换行符
// 总共进行 n*2 次操作
for (int i = 1; i <= n * 2; i++) {
String s = scanner.nextLine().trim(); // 读取整行输入并去掉多余空白字符
if (s.startsWith("h")) { // 处理头插入操作
if (idx > 0 && mk) { // 如果队列不为空并且当前有序
mk = false; // 则状态变为无序
}
idx++; // 队列元素数量增加
} else if (s.startsWith("t")) { // 处理尾插入操作
idx++; // 队列元素数量增加
} else { // 处理删除操作
if (idx == 0) // 如果队列为空,跳过操作
continue;
if (!mk) { // 如果当前状态为无序
res++; // 增加状态变化计数
mk = true; // 状态标记为有序(因为删除了一个元素)
}
idx--; // 队列元素数量减少
}
}
System.out.println(res); // 输出状态变化的次数
}
}
题目内容
有一个特异性的双端队列,该队列可以从头部或尾部添加数据,但是只能从头部移出数据。
小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×105。
所有的数据均合法。
输出描述
一个整数,表示 小A 要调整的最小次数。
样例1
输入
5
head add 1
tail add 2
remove
head add 3
tail add 4
head add 5
remove
remove
remove
remove
输出
1
说明
第1步:[1]
第2步:[1,2]
第3步:头部删除1,无需调整,还剩[2]
第4步:[3,2]
第5步:[3,2,4]
第6步:[5,3,2,4]
第7步:调整顺序为[2,3,4,5],再删除头部2,还剩[3,4,5]
第8步:头部删除3,无需调整,还剩[4,5]
第9步:头部删除4,无需调整,还剩[5]
第10步:头部删除5,无需调整
只需要调整1次