ID Codes UVA 146（求字典序比当前字符串小的最大字符串）
来源：程序员人生 发布时间：2014-10-08 19:54:35 阅读次数：2985次
说说：
题意其实很简单，就是给你一个由小写英文字母组成的字符串，然后让你求字典序比当前字符串小的最大的字符串。解法的话，就是从字符串的末尾开始遍历，若得到的子串已经是该字串所能得到的最小字典序，则继续往前遍历。否则，先在子串中，找到比原字串的首字符小的最大字符，将两者交换位置。然后将除首字符以外的其他字串排列获取最大字典序的子串即可。具体方案，看源代码好了。
源代码：
#include <stdio.h>
#include <string.h>
#define MAX 50+5
char ID[MAX];
int ismin(char*);//判断当前子串是否为最小字典序
void getans(char*);//获取比当前字符串小的最大字符串
int main(){
int i,len,offset,NO;
char* p;
// freopen("data","r",stdin);
while(scanf("%s",ID)){
if(ID[0]=='#')
break;
len=strlen(ID);
NO=1;
for(i=2;i<=len;i++){//从字符串末尾开始遍历
p=&ID[len-i];
if(!ismin(p)){
getans(p);
NO=0;
break;
}
}
if(NO)
printf("No Successor
");
else
printf("%s
",ID);
}
return 0;
}
int ismin(char* p){
int i,len;
len=strlen(p);
for(i=1;i<len;i++)
if(p[i]>p[i-1])
return 0;
return 1;
}
void getans(char* p){
int i,len,pos,j;
char temp;
len=strlen(p);
for(i=1;i<len;i++)//首先得到比当前首字符小的字符位置
if(p[i]>p[0]){
pos=i;
break;
}
for(i++;i<len;i++)
if(p[i]<p[pos]&&p[i]>p[0])//获取比当前首字符小的最大字符的位置
pos=i;
temp=p[0];
p[0]=p[pos];
p[pos]=temp;
p++;
len--;
for(i=1;i<len;i++)//将除首字符以外的子串排列获得最大字典序
for(j=0;j<len-i;j++)
if(p[j]>p[j+1]){
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
return ;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
