埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 I 二数

Description:

我们把十进制下每一位都是偶数的数字叫做“二数”。
小埃表示自己很聪明，最近他不仅能够从小数到大：2,3,4,5…，也学会了从大数到小：100,99,98…，他想知道从一个数开始数最少的数就得到一个二数。但是聪明的小森已经偷偷在心里算好了小埃会数到哪个二数，请你求出他要数到哪个数吧。
换句话说，给定一个十进制下最多105位的数字，请你求出和这个数字的差的绝对值最小的二数，若答案不唯一，输出最小的那个。
也就是说，给定数字n，求出m，使得abs(n-m)最小且m[i] mod 2 = 0

Input:

1 ≤ T ≤ 100, 1 ≤ n ≤ 10¹⁰⁰⁰⁰⁰ − 1, T组数据的数字的十进制表示长度总和不超过000000

Output:

每行一个整数 m 第 i 行表示第 i 个数所对应的“最邻近二数”

Sample Input:

5
42
11
1
2018
13751

Sample Output:

42
8
0
2020
8888

题目链接

由于题目是大数据所以用字符串处理，从左至右找到第一个奇数，若这个奇数为9则选择比输入数据小的二数(把这个奇数9减1(8)，右侧全为8)，否则判断这个奇数右侧所有数和444……444的大小关系，若大则选择比输入数据大的二数(把第一个奇数+1，右侧全为0)，反之选择比输入数据小的二数(把第一个奇数-1，右侧全为8)。不要忘记特殊判断第一个奇数是最后一位数和右侧全为4的情况。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5+5;
const double eps = 1e-5;
const double e = 2.718281828459;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        string str;
        cin >> str;
        for (int i = 0; str[i] != '\0'; ++i) {
            if ((str[i] - '0') % 2) {
                if (i == str.length() - 1) {
                    str[i] -= 1;

                }
                else if (str[i] == '9') {
                    str[i] -= 1;
                    for (int k = i + 1; str[k] != '\0'; ++k) {
                        str[k] = '8';
                    }
                }
                else {
                    bool judge_flag = 0;
                    for (int j = i + 1; str[j] != '\0'; ++j) {
                        if (str[j] != '4') {
                            if (str[j] > '4') {
                                str[i] += 1;
                                for (int k = i + 1; str[k] != '\0'; ++k) {
                                    str[k] = '0';
                                }
                                judge_flag = 1;
                            }
                            else {
                                str[i] -= 1;
                                for (int k = i + 1; str[k] != '\0'; ++k) {
                                    str[k] = '8';
                                }
                                judge_flag = 1;
                            }
                            break;
                        }
                    }
                    if (!judge_flag) {
                        str[i] -= 1;
                        for (int k = i + 1; str[k] != '\0'; ++k) {
                            str[k] = '8';
                        }
                    }
                }
                break;
            }
        }
        if (str.length() == 1) {
            str[0] = (str[0] - '0') % 2 ? str[0] - 1 : str[0];
            cout << str[0];
        }
        else {
            bool output_flag = 0;
            for (int i = 0; str[i] != '\0'; ++i) {
                if (output_flag) {
                    cout << str[i];
                }
                else if (str[i] != '0') {
                    output_flag = 1;
                    cout << str[i];
                }
            }
            if (!output_flag) {
                cout << 0;
            }
        }
        cout << endl;
    }
    return 0;
}