[CF797C] Minimal string（貪心，棧）

題目鏈接：http://codeforces.com/contest/797/problem/C

題意：給個字符串，求字典序最小的出棧順序。

一開始想用優先隊列記錄全局最小的字符，然后每次入棧的時候檢查當前字符是不是最小的，如果是那么同時pop。這樣做的話，假如不是，那么棧里面的最小就找不到了。

所以重寫，直接維護一個數組sm[i]表示i之后的字符最小的是誰。從頭掃，每次都入棧。將棧里小于等于當前位置后綴的最小字符pop輸出就行了。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 100100;
const int inf = 'z'+1;
int n;
char s[maxn], t[maxn], sm[maxn];
priority_queue<char> pq;

int main() {
    // freopen("in", "r", stdin);
    while(~scanf("%s", &s)) {
        n = strlen(s);
        sm[n] = inf;
        for(int i = n - 1; i >= 0; i--) {
            sm[i] = min(sm[i+1], s[i]);
        }
        int j = 0;
        for(int i = 0; i < n; i++) {
            t[j++] = s[i];
            while(j && t[j-1] <= sm[i+1]) {
                printf("%c", t[--j]);
            }
        }
        printf("\n");
    }
    return 0;
}

?