《编程思维与实践》1066.最小不重复数

题目

思路

一般在oj上循环$2\cdot 10^9$次以上就会超时,所以由于这题的数据A可以很大,直接循环加一再判断会超时.

优化:首先可以明确要想使不重复数尽可能小,则高位数字应该尽可能小,

即先找到最靠前的两个重复数字,然后让后一个数字加1(保证尽可能小),这样就能保证高位数字不重复且最小,

接下来只需要保证低位数字从0开始遍历,重复上述操作即可.

如:6698->6700->6701.

注意的点:

如果复用之前对大整数的处理方式,由于加法可能会进位,逆向存较为方便,所以处理时需要注意最高位在末尾.

代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 101

typedef struct{int cnt,v[N];}BIGINT;

BIGINT carry(BIGINT S,int n);   //进位 n表示进制 
BIGINT add1(BIGINT S,int pos);   //指定位置加1
int judge(BIGINT S);     //判断是否为不重复数,遇到重复返回后一位

int main()
{
	int T;
	scanf("%d",&T);
	for(int t=0;t<T;t++)
	{
		char s[N+1];
		scanf("%s",s);
        BIGINT A={strlen(s),{0}};
        for(int i=0;i<strlen(s);i++)
		{
			A.v[A.cnt-1-i]=s[i]-'0';  //逆向存
		}
		A=add1(A,0);  //先最后一位加1
		while(judge(A)!=-1)
		{
			int temp=judge(A);
			A=add1(A,temp);
            for(int i=temp-1;i>=0;i--)  //后面全赋为0
            {
                A.v[i]=0;
            }
		}
		printf("case #%d:\n",t); 
		for(int i=A.cnt-1;i>=0;i--)
        {
            printf("%d",A.v[i]);
        }
        printf("\n");
	}
	return 0;
}

BIGINT carry(BIGINT S,int n)   //进位 n表示进制 
{
	int flag=0;
	for(int i=0;i<S.cnt;i++)
	{
		int temp=S.v[i]+flag;
		S.v[i]=temp%n;
		flag=temp/n;
	}
    if(flag)   //为了加法进行的方便 可能多一位
    {
        S.v[S.cnt++]=flag;
    }
	return S;
}

BIGINT add1(BIGINT S,int pos)     //指定位置加1
{
	S.v[pos]+=1;
	S=carry(S,10);
	return S;
}

int judge(BIGINT S)   //判断是否为重复数 
{
	for(int i=S.cnt-1;i>0;i--)   //注意是逆序存
	{
		if(S.v[i]==S.v[i-1])
		{
			return i-1;   //重复的时候返回后一位
		}
	}
	return -1;   //不重复返回0 
}