51nod_1255字典序最小的子序列

作为贪心算法的某道例题，赶脚药丸啊。。这么简单的代码重构第三遍才过。。。

首先是贪心算法思想，

1，证明贪心算法有效性：
贪心策略，使用栈结构实现，遍历输入串中所有元素，对于某个元素有如下两种情况：

情况A：如果栈内已经有该元素，则废弃该元素。
情况B：如果栈内没有该元素，则废弃栈内所有“并非最后一次出现”且字典序大于当该元素的字母，遇到第一个不合法的字母则停止废弃。

对于栈内元素，我们认为任何“不被最后一次出现元素分割”的连续元素都相当按照字典序的相对大小排列整齐。基于此设定，讨论任何一个元素：

情况A：对于任何一个非最后一次出现的元素，如果大于当前元素，意味着该元素可以再后面再出现一次，因此可以废弃。且因为新插入的“当前元素”字典序最小，因而认为“原油序列可以再后面重现”且“任何废弃元素后面可以接的元素，该元素后面都可以接”。所以“如果有最优解，则一定包含最小的元素”
情况B：对于最后一次出现的元素，因为其不可能在后面出现，所以不可以将其废弃，对于该元素前面的元素，因为相对该元素较小，也不可废弃。

PS：注意一个坑，使用某元素出现此时来判断他未来会不会再出现比较好。

show the code:

#include<bits/stdc++.h>

using namespace std;

const long long MAXN=+;

char str[MAXN];

int times[];

set<char> s1;

stack<int> stack1;

int main()

{

//    cin.sync_with_stdio(false);

    memset(times,,sizeof(times));

    cin>>str;

    int len=strlen(str);

    for(int i=;i<len;++i)

    {

        times[str[i]-'a']++;

    }

    for(int i=;i<len;++i)

    {

        char ncha=str[i];

        times[ncha-'a']--;

        if(s1.count(ncha))continue;

        while(!stack1.empty())

        {

            int pos=stack1.top();

            char cha=str[pos];

            if(cha<ncha||times[cha-'a']==)break;

            if(cha>ncha)

            {

                s1.erase(cha);

                stack1.pop();

            }

        }

        s1.insert(ncha);

        stack1.push(i);

    }

    string str1;

    while(!stack1.empty())

    {

        str1.push_back(str[stack1.top()]);

        stack1.pop();

    }

    int len1=str1.length();

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

    {

        cout<<str1[i];

    }cout<<endl;

}