Codeforces Intel Code Challenge Final Round 724D. Dense Subsequence
传送门：http://codeforces.com/contest/724/problem/D
题目翻译
有个字符串，要求取其中的一些位置，使得任何连续的m个位置中至少有一个位置被取到了。然后将这些位置的字符取出，任意排序后要求字典序最小。
输出上述操作能达到的字典序最小的字符串。
题解
我们从a~z处理，如果将这个字母全取还不能满足则全取，如果可以满足，则使用贪心尽可能的少取。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int Maxn=100000; int m,len; char str[Maxn+5]; bool vis[Maxn+5]; int cnt[26]; int main(){ scanf("%d",&m); scanf("%s",str); len=strlen(str); memset(cnt,0,sizeof(cnt)); memset(vis,false,sizeof(vis)); int last=-1; for (int ty=0;ty<26;ty++){ bool flag=true; for (int now=0;now<len;now++){ if (vis[now] || str[now]-'a'==ty) last=now; if (now-last>=m){ flag=false; break; } } if (!flag){ for (int now=0;now<len;now++) if (str[now]-'a'==ty) cnt[ty]++,vis[now]=true; }else{ last=len; int preIndex=-1; for (int now=len-1;now>=0;now--){ if (vis[now]==true) last=now; if (str[now]-'a'==ty) preIndex=now; //printf("Now:%d LastId:%d Last:%d\n",now,preIndex,last); if (last-now>=m){ vis[preIndex]=true; cnt[ty]++; last=preIndex; } } break; } } for (int i=0;i<26;i++) for (int j=1;j<=cnt[i];j++) printf("%c",(char)(i+'a')); printf("\n"); return 0; } |
原文链接：Codeforces Intel Code Challenge Final Round 724D. Dense Subsequence
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!