蓝桥稍大的串

短命女 2022-06-18 02:10 135阅读 0赞

标题：稍大的串  
  
  
  串可以按照字典序进行比较。例如：  
  abcd 小于 abdc  
  
  
  如果给定一个串，打乱组成它的字母，重新排列，可以得到许多不同的串，在这些不同的串中，有一个串刚好比给定的串稍微大一些。科学地说：它是大于已知串的所有串中最小的串。你的任务就是求出这个“稍大的串”。  
  
  
例如：  
输入串：  
abfxy  
程序应该输出：  
abfyx  
  
  
再例如：  
输入串：  
ayyyxxff  
程序应该输出：  
fafxxyyy  
  
  
数据规模约定：  
  输入的串不超过1000个字符。  
  
  
特例：  
  如果已知的串已经是所有重组串中最大的，则原样输出读入的那个串。  
  
  
  
  
资源约定：  
峰值内存消耗（含虚拟机） < 256M  
CPU消耗  < 1000ms  
  
  
  
  
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。  
  
  
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。

注意：主类的名字必须是：Main，否则按无效代码处理。

思路:

找出ayyyxxff稍的串的步骤：从后往前找一个字符比它前面大的那个字母的位置，也就是y比a大，再从

这个位置往后找，找出比a稍大的字符，也就是f，交换a和f得到串fyyyxxaf, 再将f之后的字符串从小到大排得到fafxxyyy

代码：

#include<iostream>
    #include<algorithm>
    #include<string.h>
    #include<cstdio>
    using namespace std;
    int main()
    {
    	char str[1010],ch,t;
    	int i,j,k,len,c;
    	gets(str);
    	len = strlen(str);
    	for (k=len-1; k>0; k--)
    	{
    		if (str[k] > str[k-1])//k为第一个后面比前一个大的,找到其下标k 
    		 break;
    	}
    	c= k;
    	for (i=k+1; i<len; i++)
    	{
    		if (str[i]<str[c] && str[i]>str[k-1])//在k 的后面找出比str[k]大但又是最小的那个min 
    		{
    			c = i; 
    		}
    	}
    	t = str[k-1];//后面最小的且大于str[k-1]的和str[k-1]交换 
    	str[k-1] = str[c];
    	str[c] = t;
    	sort(str+k,str+len);//把后面部分排序 
    	puts(str);
    	return 0;
    }