T2 题解 - 最近回文数

Exam02

题目：

题目背景

小X最近闲来无事，开始切水题。
他看到 最近回文数 这道题，轻松打了一个数位dp。
然而他觉得数位dp有点小题大做了，想了想，用一个简单的算法，瞬间AC。
他觉得非常有趣，边来考考大家。（小X不是我，他的出处是 P2107 小Z的AK计划）

题目描述

输入一个整数，找到与它的差的绝对值最小的回文数。当有两个解时，取较小的那一个解。

输入格式

输入为一行，包括一个整数 $n$。

输出格式

输出只有一个整数，为与输入数字的差的绝对值最小的回文数。

样例输入

10000

样例输出

9999

数据范围

对于 $20\%$ 的数据， $n \leq 10^{20}$。
对于 $60\%$ 的数据， $n \leq 10^{100}$。
对于 $100\%$ 的数据， $n \leq 10^{3000}$。

乍看似乎不难：

算法（简单）

枚举差的绝对值，逐个判断是否是回文数，直到找到回文数为止。

仔细审题发现 $n$ 的长度至多为$1000$位，而 long long 也才约$10^{20}$。

可以用字符串模拟大整数。

写出代码：

#include <iostream>
#include <string>
using namespace std;
string plus_one(string n) {
    string back = n;
    int last_number = (int)n[n.size() - 1] - '0';
    if (last_number < 9) {
        back[back.size() - 1] = (char)((int)back[back.size() - 1] + 1);
    } else {
        int i = n.size() - 1;
        while (last_number == 9 && i > 0) {
            back[i] = '0';
            i--;            
            last_number = back[i] - '0';
        }
        if (last_number != 9) {
            back[i] = (char)((int)back[i] + 1);
        } else {
            back[0] = '1';
            back = back + '0';
        }
    } 
    return back;
}
string minus_one(string n) {
    string back = n;
    int last_number = (int)n[n.size() - 1] - '0';
    if (last_number > 0) {
        back[back.size() - 1] = (char)((int)back[back.size() - 1] - 1);
    } else {
        int i = n.size() - 1;
        while (last_number == 0 && i > 0) {
            back[i] = '9';
            i--;            
            last_number = back[i] - '0';
        }
        if (last_number != 1) {
            back[i] = (char)((int)back[i] - 1);
        } 
    }
    return back;
}
bool repet(string n) {
    string backn;
    for (int i = 0; i < n.size()/2; i++) {
        if (n[i] != n[n.size() - i - 1]){
            return false;
        }
    }
    return true;
}
int main() {
    string n;
    cin >> n;
    string plus_n = n;
    string minus_n = n;
    if (repet(n)){
            cout << n << endl;
            return 0;
    }
    while(minus_n.size() > 1){
        minus_n = minus_one(minus_n);
        if (true == repet(minus_n)){
            cout << minus_n << endl;
            break;
        }
        plus_n = plus_one(plus_n);
        if (true == repet(plus_n)){
            cout << plus_n << endl;
            break;
        }
    }
    return 0;
}

不要忘了时间限制（1000ms），对于超过$10^{100}$的数会非常慢。

我们需要一个效率高的算法：

算法（最终）

一位一位判断：

条件Condition

A1-如果高位小于低位且低位减高位小于等于5
A2-如果高位小于低位且低位减高位大于5
B1-如果高位不小于低位且高位减低位小于5
B2-如果高位不小于低位且高位减低位不小于5

做法Action

A1：低位赋值为高位 e.g. 155->151
A2：低位赋值为高位，低+1位+1 e.g. 159->161
B1：低位赋值为高位 e.g. 451->454
B2：低位赋值为高位，低+1位-1 e.g. 751->747

最终代码：

#include <iostream>
#include <string>
using namespace std;
string write_c(int t, char a) {
    string back = "";
    for (int i = 0; i < t; i++) {
        back += a;
    }
    return back;
}
string plus_one(string n) {
    string back = n;
    int last_number = (int)n[n.size() - 1] - '0';
    if (last_number < 9) {
        back[back.size() - 1] = (char)((int)back[back.size() - 1] + 1);
    } else {
        int i = n.size() - 1;
        while (last_number == 9 && i > 0) {
            back[i] = '0';
            i--;            
            last_number = back[i] - '0';
        }
        if (last_number != 9) {
            back[i] = (char)((int)back[i] + 1);
        } else {
            back[0] = '1';
            back = back + '0';
        }
    }
    return back;
}
string sub_one(string n) {
    string back = n;
    int last_number = (int)n[n.size() - 1] - '0';
    if (last_number > 0) {
        back[back.size() - 1] = (char)((int)back[back.size() - 1] - 1);
    } else {
        int i = n.size() - 1;
        while (last_number == 0 && i > 0) {
            back[i] = '9';
            i--;            
            last_number = back[i] - '0';
        }
        if (last_number != 1) {
            back[i] = (char)((int)back[i] - 1);
        } 
    }
    return back;
}
bool one_with_zero(string s) {
    if (s[0] != '1') {return false;}
    if (s == "1") {return false;}
    for (int i = 1; i < s.size(); i++) {
        if (s[i] != '0') {
            return false;
        }
    }
    return true;
}
string A1(string n, int high, int low) {
    n[low] = n[high];
    return n;
}
string A2(string n, int high, int low) {
    n = A1(n, high, low);
    string need_plus = n.substr(0, low);
    string other = n.substr(low);
    need_plus = plus_one(need_plus);
    n = need_plus + other;
    return n;
}
string B1(string n, int high, int low) {
    n[low] = n[high];
    return n;
}
string B2(string n, int high, int low) {
    n = A1(n, high, low);
    string need_sub = n.substr(0, low);
    string other = n.substr(low);
    need_sub = sub_one(need_sub);
    n = need_sub + other;
    return n;
}
int main() {
    string n;
    cin >> n;
    string ans = n;
    int high = 0, low = n.size() - 1;
    if (one_with_zero(n)) {
        ans = write_c(n.size() - 1, '9');
        cout << ans << endl;
        return 0;
    } 
    while ((low - high) >= 1) {
        if (ans[high] == ans[low]) {
            high++;
            low--;
            continue;
        }
        if (ans[high] < ans[low]) { // enter A
            if ((ans[low] - ans[high]) <= 5) {
                ans = A1(ans, high, low);
            } else {
                ans = A2(ans, high, low);
            }
        } else { // enter B
            if ((ans[high] - ans[low]) < 5) {
                ans = B1(ans, high, low);
            } else {
                ans = B2(ans, high, low);
            }
        }
    }
    cout << ans << endl;
    return 0;
}