学步园

如果直接对数n后面的每一个数进行判断，那复杂度有可能很大。

解题思路还是从回文数的构造出发。

分类讨论如下：

A.该数的长度是奇数（特殊情况，只有1位的，除9外直接加1,9的话输出11），取该数的前半截（包括中间数），

    1.若该数是回文数，则用前半截数值加1，之后再构造新的回文数；

     2.若不是回文数，从中间往两边找到第一个不相等的数，若前面的小于后面的，则按1处理；

若前面的大于后面的，则直接用前半截来构造回文数。

B.该数长度是偶数，取一半，后面的操作同奇数情况一样。

void lagerSmallestPlalindrome(int n)          
{
	if (n < 0)     
	{
		cout<<'0'<<endl;
		return;
	}
	char str[20];
	char temp[15];
	itoa(n,str,10);
	int len = strlen(str);
	if (len == 1)         //长度为1
	{
		if (n == 9)           //若n为9 则最近回文数为11
		{
			cout<<"11"<<endl;
		}
		else                  //若n比9小 则为n+1
		{
			cout<<n+1<<endl;
		}
	}
	else if (len%2 == 1)     //长度大于1且为奇数
	{
		for (int i = 0;i < len/2 + 1;++i)        //保存其前半部分 包括中间数
		{
			temp[i] = str[i];
		}
		temp[len/2 + 1] = '\0';
		int i,j;
		for (i = len/2 -1 ,j = len/2 + 1;j < len;--i,++j)
		{
			if (str[i] != str[j])
			{
				break;
			}
		}
		if (j == len||str[i] < str[j])     //n是回文数 或不是回文数但其前半部分小
		{
			int num = atoi(temp);       //则前半部分数值+1 再用前半部分构造回文数
			++num;
			itoa(num,temp,10);
			cout<<num;                        
			for (int i = len/2 -1;i >= 0;--i)           
			{
				cout<<temp[i];
			}
			cout<<endl;
		}
		else                   //不是回文数 但前半部分大
		{
			cout<<temp;                          //则用前半部分构造回文数
			for (int i = len/2 - 1;i >= 0; --i)
			{
				cout<<temp[i];
			}
			cout<<endl;
		}
	}    
	else                   //长度大于1且为偶数
	{
		for (int i = 0 ; i < len/2 ;++i)       //保存前半部分
		{
			temp[i] = str[i];
		}
		temp[len/2] = 0;
		if (str[len/2 - 1] == str[len/2])             //有可能是回文数
		{
			int i,j;
			for (i = len/2 - 1,j = len/2;j < len;++j,--i)
			{
				if (str[i] != str[j])
				{
					break;
				}
			}
			if (j == len||str[i] < str[j])  //n是回文数 或不是回文数但其前半部分小
			{                                    //则前数加1  用前半部分构造
				int num = atoi(temp);       //则前半部分数值+1 再用前半部分构造回文数
				++num;
				itoa(num,temp,10);
				cout<<num;                        
				for (int i = len/2 - 1;i >= 0;--i)           
				{
					cout<<temp[i];
				}
				cout<<endl;
			}
			else                               //不是回文数但其前半部分大
			{
				cout<<temp;                   //直接用前半部分构造
				for (int i = len/2 - 1;i >= 0;--i)
				{
					cout<<temp[i];
				}
				cout<<endl;
			}
		}
		else if (str[len/2 - 1] < str[len/2])          //中间靠前的数比后面的小
		{                                              //则前数加1  用前半部分构造
			temp[len/2 - 1] = char(temp[len/2 - 1] + 1);
			cout<<temp;
			for (int i = len/2 - 1;i >= 0;--i)
			{
				cout<<temp[i];
			}
			cout<<endl;
		}
		else                                       //中间靠前的数比后面的大
		{                                          //则直接用前半部分构造
			cout<<temp;
			for (int i = len/2 - 1;i >= 0;--i)
			{
				cout<<temp[i];
			}
			cout<<endl;
		}
	} 
}

参考：1.http://www.cnblogs.com/itachi7/archive/2012/07/03/2574481.html

                   2.http://blog.csdn.net/lxmuyu/article/details/8109853