Educational Codeforces Round 19 C
2024-09-29 23:32:08
Description
Petya recieved a gift of a string s with length up to 105 characters for his birthday. He took two more empty strings t and u and decided to play a game. This game has two possible moves:
- Extract the first character of s and append t with this character.
- Extract the last character of t and append u with this character.
Petya wants to get strings s and t empty and string u lexigraphically minimal.
You should write a program that will help Petya win the game.
Input
First line contains non-empty string s (1 ≤ |s| ≤ 105), consisting of lowercase English letters.
Output
Print resulting string u.
Examples
input
cab
output
abc
input
acdb
output
abdc
题意:第一个字符串的首字母放在第二个字符串的中,第二个字符串的结尾再输出,求能够得到字典序最小的字符串
解法:模拟,如果第一个字符串的首字母为最小,则直接输出,否则压入栈内,处理完毕之后再输出
#include <bits/stdc++.h>
using namespace std;
int num[];
string s;
int check(char c)
{
for(int i='a';i<c;i++)
{
if(num[i])
{
return ;
}
}
return ;
}
stack<char>q;
int main() {
ios::sync_with_stdio(false);
cin.tie();
cin>>s;
for(int i=;i<s.size();i++)
{
num[s[i]]++;
}
int cnt=;
while(cnt<s.size())
{
if(q.empty())
{
q.push(s[cnt]);
num[s[cnt]]--;
cnt++;
}
else if(check(q.top()))
{
cout<<q.top();
q.pop();
}
else
{
q.push(s[cnt]);
num[s[cnt]]--;
cnt++;
}
}
while(!q.empty())
{
cout<<q.top();
q.pop();
}
return ;
}
最新文章
- 2.0 (2)测试pymongo
- String与InputStream相互转换
- js实现缓冲运动,和匀速运动有点不相同
- 《ASP.NET1200例》解决母版页报错“内容控件必须是内容页中的顶级控件,或是引用母版页的嵌套母版页。”
- CSS动画控制器
- Hadoop的HA集群启动和停止流程
- phonegap 检查是否有网络
- 数据库里面DataTime时间类型字段,如果为null时
- 转 如何不耍流氓的做运维之——SHELL脚本
- TCP 滑动窗口
- Servlet--SingleThreadModel接口,RequestDispatcher接口
- Lintcode395 Coins in a Line II solution 题解
- SVM算法简单应用
- lambda List实现某列去重的解决方案采用扩展方法
- Nginx 配置下载附件让浏览器提示用户是否保存
- 随机生成游戏用户昵称(nodejs版本)(含机器人头像,金币等)
- Django之Models(三)
- 使用FreeMarker生成word文档
- EZ 2018 05 26 NOIP2018 模拟赛(十六)
- URL List by Category