博客

codeforces 704A (队列模拟) Thor

  • Post category:other

以下是详细讲解“codeforces 704A(队列模拟)Thor的完整攻略”：

codeforces 704A(队列模拟)Thor的完整攻略

题目描述

给定一个长度为n的字符串s，其中包含字符’?’和数字字符。现在你需要模拟一个队列，初始时队列为空。对于每个数字字符，将其加入队列的末尾。对于每个’?’字符，你需要输出队列中第一个未被输出的数字字符，并将其从队列中删除。如果队列为空，则输出-1。

输入格式

第一行包含一个整数n，表示字符串s的长度。

第二行包含一个字符串s，表示给定的字符串。

输出格式

对于每个’?’字符，输出一个整数，表示队列中第一个未被输出的数字字符。如果队列为空，则输出-1。

数据范围

1≤n≤10^5

输入样例

10
?2?4??6?8?

输出样例

2 2 4 4 6 6 8 -1

算法

本题可以使用队列模拟来解决。具体思路如下：

  • 遍历字符串s中的每个字符，如果是数字字符，则将其加入队列的末尾。
  • 如果是’?’字符，则判断队列是否为空。如果队列不为空，则输出队列的头部元素，并将其从队列中删除。如果队列为空，则输出-1。

示例

以下是C++代码示例：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n;
char s[N];
queue<int> q;

int main()
{
    cin >> n >> s;
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        if (s[i] == '?')
        {
            if (q.empty()) cout << -1 << endl;
            else
            {
                cout << q.front() << endl;
                q.pop();
            }
        }
        else if (isdigit(s[i]))
        {
            int x = s[i] - '0';
            q.push(x);
        }
    }

    return 0;
}

以下是Python代码示例：

n = int(input())
s = input().strip()

q = []
for c in s:
    if c == '?':
        if not q:
            print(-1)
        else:
            print(q.pop(0))
    elif c.isdigit():
        q.append(int(c))

示例说明

以下是两个示例，演示了如何使用队列模拟解决本题。

示例一

输入：

10
?2?4??6?8?

输出：

2 2 4 4 6 6 8 -1

解释：

首先，我们将字符串s中的每个字符遍历一遍。当遇到数字字符时，将其加入队列的末尾。当遇到’?’字符时，判断队列是否为空。如果队列不为空，则输出队列的头部元素，并将其从队列中删除。如果队列为空，则输出-1。最终，我们得到了队列中第一个未被输出的数字字符。

示例二

输入：

5
?1?2

输出：

1 1 2

解释：

首先，我们将字符串s中的每个字符遍历一遍。当遇到数字字符时，将其加入队列的末尾。当遇到’?’字符时，判断队列是否为空。如果队列不为空，则输出队列的头部元素，并将其从队列中删除。如果队列为空，则输出-1。最终，我们得到了队列中第一个未被输出的数字字符。

总结

本文介绍了codeforces 704A(队列模拟)Thor的完整攻略，包括题目描述、输入输出格式、算法思路和C++/Python代码。通过本文的介绍，读者可以更好地理解队列模拟的应用和实现方法，并在实际开发中更加灵活地使用队列模拟算法。

Tags: