学步园

UVA_146

这个题目实际上就是要求生成下一个字典序排列。

如果要是恰好比现在的字符串大一点点的话，肯定是最后连续的几位变动得越少越好，那么不妨从后往前搜，直到后面一个字符要大于前面一个字符，这时从前面那个字符一直到字符串末尾便是最小的变动区间。之后在这个区间里找到恰好比首字符大一点的字符和首字符进行交换，然后将这个区间除首字符之外按字典序排列即可。

#include<string.h>
#include<string.h>
#include<stdlib.h>
char b[60];
int cmp(const void *_p,const void *_q)
{
char *p=(char *)_p;
char *q=(char *)_q;
return *p-*q;
}
int main()
{
int i,j,k,n;
char temp;
while(1)
    {
        scanf("%s",b);
if(b[0]=='#')
break;
        n=strlen(b);
for(k=n-1;k>0;k--)
if(b[k]>b[k-1])
break;
if(k==0)
        {
            printf("No Successor\n");
continue;
        }
for(i=n-1;i>=k;i--)
if(b[i]>b[k-1])
            {
                temp=b[i];
                b[i]=b[k-1];
                b[k-1]=temp;
break;
            }
        qsort(b+k,n-k,sizeof(b[0]),cmp);
        printf("%s\n",b);
    }
return 0;    
}