http://www.spoj.pl/problems/PALIN/
【题意简述】
输入一个正整数k，输出大于k的最小回文整数。
【分析】
由于题目给的数字超级大(1000000位)，所以暴力模拟显然会严重超时，于是考虑从数的特点来求解。
首先假设一个n位10进制数字可以表示为 A[0]A[1]A[2]...A[N-1]，那么
1.我们希望从中间开始修改数字，使数增加的尽量少。
如:133151330，显然我们不会去改变它使之成为133252331，因为他显然比133161331来的大。
2.如果给你的数已经是一个Palindrome数，那你显然应该从最中间的开始改起。
如:808，显然你不会把它改成909而是把它改为818。
3.如果存在前半部分的某个数A[i]小于后半部分对应的数A[N-1-i]，那么我们必须把前半部分的那个数变成后半部分的数才能满足Palindrome的条件，可是显然这增加过多，所以我们希望在它后面的某些数A[j]拿去增加 ，这样数字变大了，而且我们不需要使A[i]变大(显然A[i]在A[j]前面几位,增加A[j]的话，数字增加的更少)。
4.如果某数全为9，那么显然它的下一个Palindrome必然为10...01,其中有(N-1)个0。
于是得到下列算法:
a.首先判断串中是否全为9，如果是则输出10..01(0有N-1个),否则转下一步。
b.用2个指针i,j指向前、后半部分，显然i从前半部分的最右边，j从后半部分的最左边开始扫描。自然这里还需要考虑到N的奇偶性，即:i=(len>>1)-1,j=i+1+(len&0x1);
c.记录对应位置的数字的大小情况，并把前半部分的内容copy到后半部分对应的位上。
d.如果存在前半部分的某些数小于后半部分的某些数，或该数本身为Palindrome数，那么进行进位操作，即从最中间开始+1.一直加到没有进位。
import java.util.*;
import java.io.*;
public class SPOJ_5
{
public static void main(String rgs[]) throws Exception
{
BufferedReader stdin =
new BufferedReader(
new InputStreamReader(System.in));
String s = stdin.readLine();
int m,t = Integer.parseInt(s);
int[] dp=new int[1000002];
for(m=0;m<t;m++){
s = stdin.readLine();
StringBuilder str=new StringBuilder(s);
int len=str.length(),i,j;
boolean alln=true;
for(i=0;i<len && alln;i++){
if(str.charAt(i)!='9')
alln=false;
}
if(alln){
System.out.print("1");
for(i=0;i<len-1;i++)
System.out.print("0");
System.out.println("1");
continue;
}
boolean flag=true;;
i=(len>>1)-1;
j=(len>>1)+(len&0x1);
Arrays.fill(dp,0);
while(j<len){
if(str.charAt(i)>str.charAt(j))
dp[j]=-1;
else if(str.charAt(i)<str.charAt(j))
dp[j]=1;
i--;
j++;
}
i=(len>>1)+(len&0x1);
while(i<len){
if(dp[i]==-1)
break;
if(dp[i]==1){
flag=false;
break;
}
i++;
}
if(i==len)
flag=false;
for(i=(len>>1)+(len&0x1);i<len;++i){
if(dp[i]!=0)
str.setCharAt(i,str.charAt(len-1-i));
}
if(!flag){
i=(len>>1);
if(len%2==0)
i--;
int buf=1;
while((buf==1) && (i>=0)){
buf=(str.charAt(i)+1-'0')/10;
int p=(int)(str.charAt(i)-'0'+1)%10;
char c=(char)(p+48);
str.setCharAt(i,c);
str.setCharAt(len-1-i,c);
i--;
}
}
System.out.println(str);
}
}
}posted on 2009-08-26 10:35
飞翔天使 阅读(314)
评论(0) 编辑 收藏 所属分类:
spoj