最小回文数

题目描述

回文数是从左向右读和从右向左读结果一样的数字串。

例如：121、44 和3是回文数，175和36不是。

对于一个给定的N，请你寻找一个回文数P，满足P>N。

满足这样条件的回文数很多，你的任务是输出其中最小的一个。

输入格式

1行，一个正整数N。N的数值小于10^100，并且N没有前导0。

输出格式

你的程序应该输出一行，最小的回文数P（P>N）。

输入输出样例

输入 #1复制

44

输出 #1复制

55

说明/提示

50%的数据，N<10^9

100%的数据，N<10^100

输入一个整数 ABCD ，若整数ABBA 比 ABCD 大，则 ABBA 就是比它大的最小回文数，然后就可以直接输出这个答案了。

而如果 ABBA 比 ABCD 要小（或等于）那我们就要找到比 ABBA 大的下一个回文数。

不难发现它就是：ACCA 且 C=B+1。

#include<cstdio>
#include<cstring> 
using namespace std;

char a[1002];

int b[1002],s[1002],t[1002];

int l,mid1,ls=0;

void add(){
    int i,x,y;
    i=mid1+1;
    x=b[i]+1;
    b[i]=x%10;
    y=i;
    if(l%2==0){
        b[i-1]=b[i];
        y=i-1;
    }
    while(x>9){
        i++;
        x=b[i]+1;
        b[i]=x%10;
        y--;
        x=b[y]+1;
        b[y]=x%10;
    }   
}

void hw(){
    int top=0,j,next;
    for(j=0;j<=mid1;j++){
        s[++top]=b[j];
    }
    if(l%2==0){
        next=mid1+1;
    }
    else{
        next=mid1+2;
    }
    for(j=next;j<l;j++){
        t[top]=b[j];
        ls++;
        top--;
    }
    for(j=0;j<=mid1;j++){
        b[j]=t[++top];
    }
}

int com(){
    int i;
    for(i=ls;i;i--){
        if(s[i]<t[i])
            return 0;
        else{
            if(s[i]>t[i]){ 
                return 1;
            }
        }
    }
    return 1;
}

int main(){
    int i,p;
    scanf("%s",a);
    l=strlen(a);
    for(i=0;i<l;i++){     
        b[i]=a[l-i-1]-'0';
    }
    for(p=0;p<l;p++){
        if(b[p]!=9){
            break;
        }
    }
    if(p==l){
        printf("1");
        for(i=0;i<l-1;i++){
            printf("0");
        }
        printf("1");
        return 0;
    }
    mid1=l/2-1;
    hw();
    if(com()){
        add();
    }
    for(i=l-1;i>=0;i--){
        printf("%d",b[i]);
    }
    return 0;
}