Codeforces724D [字符串][乱搞][贪心]

/*
不要低头，不要放弃，不要气馁，不要慌张
题意：给你一个区间长度n和一个字符串，要求在字符串中选择一些symbol使得字符串的任意长度为n的子区间都存在至少一个symbol。
任意选取symbol，输出符合条件的symbol所有集合按照任意顺序排序的字典序最小的字符串。
思路：
1.明确 aaab 的字典序要小于aab。而aaab的字典序要小于aaabb。
那么假如从a到x（x是某个字母）全部采用也无法符合题意，但是从a到x+1全部采用能符合题意。
我们需要做的是，找最少需要多少个x+1使得在采用a到x所有字母的前提下，使用尽量少的x+1符合题意。
2.以下思路可能过绕。（因为看别人AC代码很短）所以慎入。
aft[i][j]代表在第i个位置以后距离第i个位置最近的j字母距离第i个位置的距离。
然后每加入一个字母就用now[i]更新，代表距离第i个位置以后第i个位置最近的被选为symbol的字母距离第i个位置的距离。
然后找到刚才提到的x+1以后就可以贪心得安排选取哪些使得采用的数目最小。
坑：坑在最后的贪心啦。这题做完以后，我对自己的逻辑产生了很大的质疑...以后逻辑要多靠脑子想，不能一味依赖手动检测，否则效率太低了...嗷嗷

*/

#include<bits/stdc++.h>
using namespace std;
char jilu[100050];
int shu[100050];
int bbf[100050][28],aft[100050][28],me[100050][28],now[100050],bf[100050];
int gg[30];
int rel[100050];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",jilu);
    int len=strlen(jilu);
    for(int i=0;i<len;i++){
        shu[i]=jilu[i]-'a';
    }
    for(int i=0;i<len;i++){
        gg[shu[i]]++;
    }
    for(int i=0;i<26;i++){
        int st=-1e9;
        for(int j=0;j<len;j++){
            if(shu[j]==i)st=j;
            bbf[j][i]=st;
        }
        st=1e9;
        for(int j=len-1;j>=0;j--){
            if(shu[j]==i)st=j;
            aft[j][i]=st;
        }
        for(int j=0;j<len;j++){
            me[j][i]=aft[j][i]-j+1;
        }
    }
    for(int i=0;i<26;i++){
        bool ok=1;
        for(int j=0;j<=len-n;j++){
            bf[j]=now[j];
            if(i==0)now[j]=me[j][i];
            else now[j]=min(now[j],me[j][i]);
            if(now[j]>n)ok=0;
        }
        if(ok){
            int num=0;
            if(i==0){
                for(int j=0;j<=len-n;j++){
                    rel[j]=j;
                }
                num=len-n+1;
            }
            else{
                for(int j=0;j<=len-n;j++){
                    if(bf[j]>n)rel[num++]=j;
                }
            }
            for(int j=0;j<i;j++){
                for(int k=0;k<gg[j];k++)printf("%c",'a'+j);
            }
            int aaa=0,bbb=0,bf=-1;
            bool ook=0;
            while(bbb<len){
                if(shu[bbb]==i){
                    if(bbb-rel[aaa]+1>n){
                        ook=1;
                        printf("%c",'a'+i);
                        while(aaa<num&&rel[aaa]<=bf){
                            aaa++;
                        }
                    }
                    if(aaa==num)break;
                    bf=bbb;
                }
                bbb++;
            }
            if(!ook||aaa!=num)printf("%c",'a'+i);
            break;
        }
    }
    return 0;
}