Codeforces 797C - Minimal string

C. Minimal string

题目链接：http://codeforces.com/problemset/problem/797/C

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
题目大意：略。
方法：栈顶的优先级大于后缀的优先级，则出栈。
代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<stack>

using namespace std;

const int N=1e5+;

int main()

{

    char s[N];

    gets(s);

    int n=strlen(s);

    char best[N];

    best[n]='z';

    for(int i=n-;i>=;i--)

    {

        best[i]=min(best[i+],s[i]);

    }

    stack<char>v;

    int cur=;

    while(!v.empty()||cur<n)

    {

        if(!v.empty()&&v.top()<=best[cur])

        {

            putchar(v.top());

             v.pop();

        }

        else v.push(s[cur++]);

    }

    cout<<endl;

    return ;

}

巴特西

Codeforces 797C - Minimal string

最新文章

热门文章