上海市计算机学会竞赛平台2022年11月月赛丙组出栈序列
发布时间
阅读量：
阅读量
题目描述
给定一个长度为𝑛n的、仅由小写字母组成的字符串，将其按序依次放入栈中。
请问在所有可能的出栈序列中，字典序最小的出栈序列是多少？
输入格式
输入第一行， 一个正整数𝑛n
输入第二行，一个长度为𝑛n的字符串
输出格式
输出所有出栈序列中，字典序最小的出栈序列
数据范围
- 对于30%30%的数据，1≤𝑛≤101≤n≤10
- 对于60%60%的数据，1≤𝑛≤1031≤n≤103
- 对于100%100%的数据，1≤𝑛≤1051≤n≤105
样例数据
输入:
3
yes
输出:
esy
说明:
字符y、e、s依次进栈，所有出栈的可能性有：
{yes}、{yse}、{eys}、{esy}、{sey}
其中 {esy} 的字典序最小
详见代码:
#include <bits/stdc++.h>
using namespace std;
string a;
char b[100005];
string ans = "";
stack<char> s;
int n;
int main()
{
cin >> n;
cin >> a;
b[n]='z';
for (int i = n - 1; i >= 0; i--)
{
b[i] = min(b[i+1],a[i]);
}
for (int i = 0; i < n; i++) {
while(!s.empty() && s.top() <= b[i])
{
ans += s.top();
s.pop();
}
if (a[i] == b[i])
{
ans += a[i];
}
else
{
s.push(a[i]);
}
}
while (!s.empty())
{
ans += s.top();
s.pop();
}
cout << ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~