[SPOJ] PALIN – The Next Palindrome

原题: http://www.spoj.com/problems/PALIN/


题目大意: 给任意一个数, 找到比这个数大的最小的一个回文数字.


分析: 这题要考虑的情况很多, 比如例子中的808, 我们需要把0改成1, 因为如果我们改动最后的8, 前边的8也要增加, 所以改变的总量会更大, 只能改变0. 所以第一条就是, 我们要从数字的中间改. 另一个是2133变成2222. 这个改变的过程是2133->2132->2112->2222, 这里, 我们用的是meet in mid的策略, 我们要比较前边和后边的数字, 如果他们是一样的, 那么就忽略, 如果他们不一样, 前边比后边大, 就把后边改成前边的, 这样相当于增加了,所以就结束了. 如果后边大, 把前边赋值后边, 但是继续程序.最后一种情况是, 99999->100001. 我们把所有的9变成0, 然后最后的9变成1,然后前边加1.