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[];
int shu[];
int bbf[][],aft[][],me[][],now[],bf[];
int gg[];
int rel[];
int main()
{
int n;
scanf("%d",&n);
scanf("%s",jilu);
int len=strlen(jilu);
for(int i=;i<len;i++){
shu[i]=jilu[i]-'a';
}
for(int i=;i<len;i++){
gg[shu[i]]++;
}
for(int i=;i<;i++){
int st=-1e9;
for(int j=;j<len;j++){
if(shu[j]==i)st=j;
bbf[j][i]=st;
}
st=1e9;
for(int j=len-;j>=;j--){
if(shu[j]==i)st=j;
aft[j][i]=st;
}
for(int j=;j<len;j++){
me[j][i]=aft[j][i]-j+;
}
}
for(int i=;i<;i++){
bool ok=;
for(int j=;j<=len-n;j++){
bf[j]=now[j];
if(i==)now[j]=me[j][i];
else now[j]=min(now[j],me[j][i]);
if(now[j]>n)ok=;
}
if(ok){
int num=;
if(i==){
for(int j=;j<=len-n;j++){
rel[j]=j;
}
num=len-n+;
}
else{
for(int j=;j<=len-n;j++){
if(bf[j]>n)rel[num++]=j;
}
}
for(int j=;j<i;j++){
for(int k=;k<gg[j];k++)printf("%c",'a'+j);
}
int aaa=,bbb=,bf=-;
bool ook=;
while(bbb<len){
if(shu[bbb]==i){
if(bbb-rel[aaa]+>n){
ook=;
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 ;
}
上一篇:Objective-C中的单例模式(工具类)


下一篇:opencv::直方图均衡化