14329: 【原4329】市原大辅的最小串

题目

题目描述

author: codeforces 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4329

Description

市原大辅在生日那天收到了一个字符串$s (1 \leq |s| \leq 10^5)$ 作为礼物。 他又拿了两个空串$t$和$u$决定玩游戏。 该游戏有两个可能的动作：

提取s的第一个字符，并附加此字符到$t$的末尾。

提取t的最后一个字符，并附加此字符到$u$的末尾。

市原大辅希望使字串s和t为空，并且按字典顺序最小化字串$u$。

请你编写一个程序，以帮助市原大辅赢得比赛。

Input Format

一行，包含长为$|s|$的小写英文字符串$s$。($1 \leq |s| \leq 5000$)

Output Format

输出答案的$u$。

Sample Input 1

cab

Sample Output 1

abc

Sample Input 2

acdb

Sample Output 2

abdc

zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
char s[100005];
int n, cnt[26] = {0};
char ans[100005], st[100005];
void init(){
    scanf("%s", s);
    n = strlen(s);
    REP(i, 0, n - 1)
        ++cnt[s[i] - 'a'];
}
void solve(){
    int top = 0, cur = 0;
    int l = 0;
    REP(i, 0, 25){
        while (top && st[top] <= i + 'a')
            ans[l++] = st[top], --top;
        while (cnt[i]){
            if (s[cur] == i + 'a'){
                ans[l++] = i + 'a';
            }else {
                st[++top] = s[cur];
            }
            --cnt[s[cur] - 'a'];
            ++cur;
        }
    }
    while (top)
        ans[l++] = st[top], --top;
    ans[n] = '\0';
    printf("%s\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}