给一个长度为n的字符串，找出长度为m的最小字典子序列

头条一面挂了，除了自己菜，数据结构和基础知识理解深刻外，还有就是面试时紧张得肚子疼到抽搐。。。可能是绝症了

言归正传，面试官本来想随便出个签到题玩一下开个场，结果被我紧张的崩了。
结束面试之后冷静下来认真想了下并不难

题目是，给出一个长度为n(1<n<10000)的只有小写字母的字符串，然后找出一个长度为m的最小字典子序列。
如 orange
当m=3时，输出结果age

若borange,且长度为3时，同样输出age

面试的时候脑子一团浆糊，想到了标号和排序，直接被反例否定了。

如果用最暴力的思想，找到n个字符里字典序最小的字母，然后砍去这个字母之前的字母，在剩余的字母中又找一个字典序最小的字母，这样一直找n个就好了。
唯一要考虑的条件就是，这样不断贪心取最小的要求是，要保证取了某个字母后，剩余待选串中的字符个数要大于等于m。

于是想到一个复杂度为O(n*m)的做法，每次遍历n字符串，查找符合条件的字符，再从头扫一遍找下一个字符。从头扫的原因是，当找到了一个字符，比如b，无法判断是否后面的字符是否存在一个字典序小于b的字符，所以仍要遍历完整个串才能得到一个最小值。

那么做一个预处理，首先26个vector存储每个字母出现位置的下标，O(n)遍历字符串，push进每个字母出现下标，因为是顺序遍历，所以每个vector都是有序的。
然后遍历m次这26个vector，找出第一个字母的出现位置，满足<=n-(m-i)+1,说明存在一个较小的字母符合筛选条件，并且不用关心该位置剩余字符串是否存在比其更小的字母，如果存在，在字典序遍历其他vector就应该找到了。在ans中填入这个字母，然后从a字母开始继续查找下标大于上一个填入ans中字母下标的符合条件的字母。这个在有序vector中查找位置直接用二分即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
char a[10080];
vector<int>pos[26];
int main()
{
    int n,m;
    char ans[10080];
    while(scanf(\"%d\",&n)!=EOF)
    {
        for(int i=0;i<=26;i++)pos[i].clear();
        scanf(\"%d\",&m);
        scanf(\"%s\",a);
        for(int i=0; i<n; i++) pos[a[i]-\'a\'].push_back(i+1);
        memset(ans,0,sizeof ans);
        int tmp=0;
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<26; j++)
            {
                if(pos[j].size()!=0)
                {
                    int num=pos[j][upper_bound(pos[j].begin(),pos[j].end(),tmp)-pos[j].begin()];
                    if(num>tmp&&num<=n-m+i+1)
                    {
                        tmp=num;
                        ans[i]=\'a\'+j;
                        break;
                    }
                }
            }
        }
        printf(\"%s\\n\",ans);
    }
}