問題 G: 最小的回文數
時間限制: 1 Sec 內存限制: 32 MB
[提交][狀態][討論版]
題目描述
回文數是從前往后和從后往前得到的數是相同的。
現給你一個正整數N，請你找到比N大的最小的那個回文數P。
輸入
輸入包含多組測試數據。
每組輸入一個正整數N，N不超過10000位，并且N不包含前導0。
輸出
對于每組輸入，輸出比N大的最小的那個回文數P。
樣例輸入

44 3 175

樣例輸出

55 4 181

提示
/*
解題思路：
字符串處理。
分為原來使回文，原來不是回文兩部分來處理。
原來是回文，要特殊考慮一下全是9的情況，直接輸出一個1，然后length-1個0，最后加一個1。
原來是回文且不全是9，只需要從對稱軸開始找第一對不為9的+1就OK(長度為奇數我當中間同一個數為一對)
原來不是回文，明確一點，不能變小！
所以 對稱軸左邊的值 先賦值 給它們對稱的位置
這讓原來不是回文的變成了一個回文，但是并不能保證它沒有變小。
所以變成回文后，與原來的那個串比較一下，如果比之前大，那這個就是結果。
如果沒有比之前大，那就把這個串（已經變成了回文串）按原來那樣是回文的時候一樣處理就行！
*/

ac_code:

#include <bits/stdc++.h> using namespace std; const int maxn = 1e4 + 5; char s[maxn]; char st[maxn]; void solve(char * s,int cnt,int len) {int t = len&1 ? len/2 : len/2-1;int pos = t;if(cnt == len){printf("1");for(int i = 1; i < len; i++){printf("0");}printf("1\n");return;}if(s[pos] != '9'){s[pos] = s[len-1-pos] = s[pos]+1;}else{while(s[pos] == '9' && pos >= 0){s[pos]=s[len-1-pos] = '0';pos--;}s[pos] = s[len-1-pos] = s[pos]+1;}printf("%s\n",s);return; } int main() {while(~scanf("%s",s)){int len = strlen(s);int flag = 1,cnt = 0;for(int i = 0,j = len-1; i <= j; i++,j--){if(s[i] != s[j]){flag = 0;break;}if(s[i]=='9') i==j ? cnt += 1 : cnt += 2;}if(flag){solve(s,cnt,len);}else{memset(st,'\0',sizeof(st));strcpy(st,s);cnt = 0;for(int i = 0,j = len-1; i <= j; i++,j--){if(st[i] != st[j]){st[j] = st[i];}if(st[i]=='9') i==j ? cnt += 1 : cnt += 2;}if(strcmp(st,s)>0)printf("%s\n",st);elsesolve(st,cnt,len);}memset(s,'\0',sizeof(s));}return 0; }

總結

以上是生活随笔為你收集整理的问题 G: 最小的回文数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。