题目描述

难度分:$1100$

输入$T(\leq 10^4)$表示$T$组数据。每组数据输入$n(1 \leq n \leq 10^9)$。

定义$digsum(a)$表示$a$的数位和。构造两个非负整数$x$和$y$，满足$x + y=n$且$|digsum(x) - digsum(y)| \leq 1$。

可以证明，这样的$x$和$y$一定存在。

输入样例

5
1
161
67
1206
19

输出样例

1 0
67 94
60 7
1138 68
14 5

算法

构造

如果$n$是偶数，那么$x=y=\frac{n}{2}$，两者的数位和完全相等。如果$n$是奇数，就从高到低遍历$n$的数位$d$，逐位构造$x$和$y$。如果$d$是偶数，让$x$和$y$在这一位均分$d$；如果$d$是奇数，就让数位和小的那个数获得$\lceil \frac{n}{2} \rceil$，数位和大的那个数获得$\lfloor \frac{n}{2} \rfloor$。

复杂度分析

时间复杂度

当$n$是奇数时，需要遍历它的各个数位，因此单个$case$的时间复杂度为$O(log_{10}n)$。$T$个$case$的时间复杂度为$O(Tlog_{10}n)$。

空间复杂度

由于从高到低遍历$n$的数位，所以将$n$转化为字符串遍历会更方便。字符串的长度为$O(log_{10}n)$，预留这部分空间给每个$case$使用即可。因此，额外空间复杂度为$O(log_{10}n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
int t, n;

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        if(n&1) {
            string s = to_string(n);
            bool gt = false, lt = false;
            int num1 = 0, num2 = 0;
            for(int i = 0; i < s.size(); i++) {
                int d = s[i] - '0';
                if(d&1) {
                    if(gt) {
                        int d1 = d>>1, d2 = d + 1>>1;
                        num1 = 10*num1 + d1;
                        num2 = 10*num2 + d2;
                        gt = false;
                        lt = true;
                    }else {
                        int d1 = d + 1>>1, d2 = d>>1;
                        num1 = 10*num1 + d1;
                        num2 = 10*num2 + d2;
                        gt = true;
                        lt = false;
                    }
                }else {
                    int d1 = d>>1, d2 = d>>1;
                    num1 = 10*num1 + d1;
                    num2 = 10*num2 + d2;
                }
            }
            printf("%d %d\n", num1, num2);
        }else {
            printf("%d %d\n", n>>1, n>>1);
        }
    }
    return 0;
}