P1609 最小回文数 题解

本题位数较大，所以只能使用字符串读入

因为是回文数，所以我们只考虑前半部分的情况就能确定一个回文数。

如一个型为 $\overline{xyz}$ 的数，我们考虑 $\overline{xyx}$（这个数是回文数）是否大于 $\overline{xyz}$，如果大于，那么就可以输出 $\overline{xyx}$，否则就把 $y$ 自增 $1$，并且考虑进位（详情见高精度），直到我们求出的数大于原数为止。

这里要特判一下，如果输入是 $9$，我们就直接输出 $11$。

这题和 SP5 相似，双倍经验等着你！

不多说了，上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1000010],p[1000010],l;
char s[1000010];
bool palin(int x[],int y[])
{
	for(int i=0;i<l;i++) if(x[i]!=y[i]) return x[i]<y[i];
	return false;
}
int main()
{
	scanf("%s",s),l=strlen(s);
	if(strcmp(s,"9")==0)
	{
		cout<<11<<endl;
		return 0;
	}
	for(int i=0;i<l;i++) a[i]=s[i]-'0';
	for(int i=0;i<=(l-1)/2;i++) p[i]=p[l-i-1]=a[i];
	if(!palin(a,p))
	{
		a[(l-1)/2]++;
		for(int i=(l-1)/2;i;i--) a[i-1]+=a[i]/10,a[i]%=10;
		for(int i=0;i<=(l-1)/2;i++) p[i]=p[l-i-1]=a[i];
	}
	for(int i=0;i<l-1;i++) cout<<p[i];
	if(p[l-1]==10) cout<<1<<endl;
	else cout<<p[l-1]<<endl;
	return 0;
}