华为OD机试真题 C++ 实现【特异性双端队列 、 最小调整顺序次数 、 最小的调整次数】_华为od 特异性双端队列 、 最小调整顺序次数 、 最小的调整次数

题目

        给定一个队列，但是这个队列比较特殊，可以从头部添加数据，也可以从尾部添加数据，但是只能从头部删除数据。输入一个数字n，会依次添加数字1~n（也就是添加n次）。

        但是在添加数据的过程中，也会删除数据，要求删除必须按照1~n按照顺序进行删除，所以在删除时，可以根据需要调整队列中数字的顺序以满足删除条件。

输入描述：

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

接下来的2N行是添加和删除语句。其中：head add x 表示从头部添加元素 x，tail add 表示从尾部添加元素，remove表示删除元素。

输出描述：

输出一个数字，表示最小的调整顺序次数。

示例：

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]

第8步：头部删除3，无需调整，还剩[4，5]

第9步：头部删除4，无需调整，还剩[5]

第10步：头部删除5，无需调整

只需要调整1次

思路

1：按照题目要求模拟整个过程即可，栈和队列的考察

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
    string str;
    getline(cin, str);
    int N = stoi(str);
    int result = 0;
    bool inorder = true; // 有序
    int size = 0;
    for(int i = 0; i < N * 2; i++) {
        getline(cin, str);
        istringstream ss(str);
        ss >> str;
        if(str == "remove") {
            if(size == 0) {
                continue;
            } else {
                if(inorder == false) {
                    result++;
                    inorder = true;
                }
                size--;
            }
        } else {
            if(str == "head" && size != 0) {
                inorder = false;
            }
            size++;
        }
    }
    cout << result << endl;
    return 0;
}