赣州建站_合肥营销型网站建设开发_seo优化排名营销_seo销售代表招聘

回顾

Dedicated to you.

• 湘大 OJ 代码仓库
• A+B III
• 问题 H: 三角数
• 问题 G: 3个数
• 等式 数组下标查询，降低时间复杂度
• 1405 问题 E: 世界杯

题目

数码串，你从左到右，依次将数码a取出来，不断执行下面的操作，直到遍历了所有的数码。
1.如果d比后面相邻的数码大，那么就把这个数码取出来，将min{d +1,9}放到数的最后面
2.移动到下一个数码
请问完成上面的所有步骤后，你获得的数码串是什么?

思路

1.感觉有一个点非常不好想，只能积累这种做法，就是，我们不是把输入的字符串遍历一遍就结束了，因为会产生新的字符串，或者说新的数字，我们也需要处理新的产生的数字。正是因为这样，我们的数组空间不是 $10^5\ast 2$ ，因为仅仅遍历一遍字符串，再存一遍新的字符串还不够。

2.观察可以发现，最后输出的答案是按照升序排列好的，我们需要考虑最坏情况下，需要多大的数组空间。每一个数码只有 $10$ 种可能的取值，最坏的情况就是一个数码从 $1$ 变到 $2$ ，再变到 $3$ ，一直变到 $9$ ,也就是说最多变 $8$ 次，所以极限的来说，数组空间开到这个大小就足够了。$100010\ast 8$ ，笔者测试了一下，确实是可以的。但是一般取 $10$ 的整数倍，所以实际代码写的是 $1000010$.

3.另外说一些代码细节，start 表示的是一个指针，最开始的时候指向第一个元素，字符数组 \0 表示的是空，也就是假设我定义一个全局字符数组，里面的元素全是 \0

4.start<len-1 表示的是，c[len-1] 表示最后一个元素（数组下标从 $0$ 开始计数），不取等号的原因是指针指到倒数第二个元素，比较倒数第二个元素和最后一个元素

5.最后面我把更新的数码存到的是 c[len] ，为什么我不把 c[len] 输出出来，而是只输出到 c[len-1] 呢？

for(int i=0;i<len;i++){if(c[i]!='\0'){printf("%c",c[i]);}
}

因为最后 len++ 会多加一位。

c 语言代码

#include<stdio.h>
#include<string.h>
char c[1000010];int main(){int t;scanf("%d",&t);while(t--){scanf("%s",c);int start=0;int len=strlen(c);while(start<len-1){if(c[start]=='\0'||c[start]<=c[start+1]){start++;}else{if(c[start]+1<='9'){c[len]=c[start]+1;}else{c[len]='9';}c[start]='\0';len++;}}for(int i=0;i<len;i++){if(c[i]!='\0'){printf("%c",c[i]);}}puts("");}return 0;
}