[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.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int t = in.readInt();
        for (int i = 0; i < t; i++) {
            solve(in.readLine(), out);
        }
    }

    public void solve(String s, OutputWriter out) {
        char[] str = s.trim().toCharArray();
        boolean flag = false;
        int length = str.length;
        int i = 0;
        int j = length - 1;
        while (i <= j) {
            if (str[j] < str[i])
                flag = true;
            str[j] = str[i];
            i++;
            j--;
        }
        if (flag) {
            out.printLine(String.valueOf(str));
            return;
        }
        i--;
        if (str[i] != '9') {
            str[i]++;
            str[length - 1 - i] = str[i];
            out.printLine(String.valueOf(str));
            return;
        }
        else {
            while (i >= 0 && str[i] == '9') {
                str[length - 1 - i] = '0';
                str[i] = '0';
            }
            if (i >= 0) {
                str[i]++;
                str[length - 1 - i] = str[i];
                flag = true;
            }
            if (flag) {
                out.printLine(String.valueOf(str));
                return;
            }
            out.printLine(1+String.valueOf(str)+1);
            return;
        }

    }