首页 > 代码库 > Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)D Dense Subsequence
Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)D Dense Subsequence
传送门：D Dense Subsequence
题意：输入一个m，然后输入一个字符串，从字符串中取出一些字符组成一个串，要求满足：在任意长度为m的区间内都至少有一个字符被取到，找出所有可能性中字典序最小的情况，并按字典序输出
思路：字典序 例如 aaaaaaab < ab 也就是说，如果满足要求的取法中取到了b 那么所有的a都应该被取到，这样才可以保证字典序最小，那么也就是说在26个字母中找到一定要被取的最大字母，然后再确定最大的字母的个数，比它小的全部要取
AC代码：
1 #include "stdio.h" 2 #include "string.h" 3 int main() 4 { 5 int m,k,flag,i,j,c[30],now; 6 char s[100005]; 7 while(scanf("%d",&m)!=EOF) 8 { 9 getchar();10 gets(s);11 memset(c,0,sizeof(c));12 int l=strlen(s);13 for(j=0+‘a‘; j<26+‘a‘; j++)14 {15 k=0;flag=1;16 for(i=0; i<l; i++)17 {18 k++;19 if(s[i]<=j)20 {21 k=0;22 if(s[i]==j) c[j-‘a‘]++;23 }24 if(k>=m)25 flag=0;26 }27 if(flag) break;28 }29 k=0;c[j-‘a‘]=0;now=0;30 for(i=0; i<l; i++)31 {32 k++;33 if(s[i]<j)34 k=0;35 else if(s[i]==j)36 now=i;37 if(k==m)38 {39 k=0;40 i=now;41 c[j-‘a‘]++;42 }43 }44 for(i=0; i<=26; i++)45 { //printf("%d ",c[i]);46 for(j=0; j<c[i]; j++)47 printf("%c",i+‘a‘);48 }49 printf("\n");50 }51 return 0;52 }
Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)D Dense Subsequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。