CF - 797C. Minimal string - 贪心+栈处理+字符串处理

题目描述： C. Minimal string time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

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

题意概述：给出string s长度<=1e5, op1:把s的第一个字符移动到t末尾.op2:把t最后一个字符移到u末尾,求u能得到的最小字典序?解题思路：先预处理每个字符个数，那么在输出第i位时候，先把它压人栈内，判断栈顶的字符是不是当前状态下字典序最小的字符，如果是则把栈内全部字符输出，不是则继续。AC代码： #include <bits/stdc++.h> #define INF 0x3f3f3f3f #define maxn 100100 #define lson root << 1 #define rson root << 1 | 1 #define lent (t[root].r - t[root].l + 1) #define lenl (t[lson].r - t[lson].l + 1) #define lenr (t[rson].r - t[rson].l + 1) #define N 1111 #define eps 1e-6 #define pi acos(-1.0) #define e exp(1.0) using namespace std; const int mod = 1e9 + 7; typedef long long ll; typedef unsigned long long ull; int vis[26]; string str; stack<char> s; vector<int> ans; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif while (cin >> str) { memset(vis, 0, sizeof(vis)); ans.clear(); while (!s.empty()) s.pop(); int len = str.length(); for (int i = 0; i < len; i++) vis[str[i] - 'a']++; for (int i = 0; i < len; i++) { int pos = str[i] - 'a'; s.push(pos); vis[pos]--; bool flag = 1; while (!s.empty()) { int cur = s.top(); for (int i = 0; i < cur; i++) if (vis[i]) { flag = 0; break; } if (!flag) break; ans.push_back(cur); s.pop(); } } int sz = ans.size(); for (int i = 0; i < sz; i++) printf("%c", ans[i] + 'a'); puts(""); } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }