题目链接

数位差与数值和的构造

题目描述

给定一个整数 ，请找到两个非负整数 和 ，满足以下两个条件：

  2. 的数字和与 的数字和之差的绝对值不超过 1。

题目保证解总是存在的，若有多组解，输出任意一组即可。

解题思路

这是一个构造性问题。我们需要将一个数 拆分为两个数 和 ，同时满足数值和与数字和两方面的约束。

1. 核心构造思想

要确保 这个条件成立，最直接的方法是按位构造。也就是说，我们将 的每一位数字 都拆分成两个数字 和 ，使得 。如果 的所有位都遵循这个规则，那么将 和 构成的数 和 相加，结果必然是 。

例如，如果 ，我们可以将其看作 。

  • 对于百位的 1，我们可以拆成 1 和 0。
  • 对于十位的 6，我们可以拆成 3 和 3。
  • 对于个位的 1，我们可以拆成 0 和 1。
  • 那么 , 。。

2. 如何满足数字和的约束

在按位构造的基础上，我们要让 和 的数字和之差尽可能小。最理想的策略就是对 的每一位数字 进行“均分”。

  • 如果 是偶数：我们可以完美地把它均分为 和 。将这两个相等的部分分别分配给 和 的对应位。这样，它们对各自总数字和的贡献是相等的，不会引入任何差值。

  • 如果 是奇数：我们无法完美均分，只能拆成 和 。例如，7 只能拆成 3 和 4。这会给 和 的数字和带来 1 的差距。为了保持最终总数字和的平衡，我们可以轮流将较大的部分分配给 和 。

3. 最终算法

我们可以设置一个轮换标志（例如 turn_A），初始为真。然后从高位到低位遍历 的每一位数字 ：

  1. 计算 的一半：。
  2. 如果 是偶数，则 和 的对应位都分配 。
  3. 如果 是奇数，则根据轮换标志：
    • 如果 turn_A 为真，则 的对应位分配 ， 的对应位分配 。然后将 turn_A 设为假。
    • 如果 turn_A 为假，则 的对应位分配 ， 的对应位分配 。然后将 turn_A 设为真。

将 当作字符串处理，可以方便地遍历每一位并构造出 和 的字符串形式，最后再转换为整数输出。

代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    string n_str;
    cin >> n_str;

    string a_str = "", b_str = "";
    bool turn_A = true;

    for (char c : n_str) {
        int digit = c - '0';
        int half = digit / 2;
        if (digit % 2 == 0) {
            a_str += to_string(half);
            b_str += to_string(half);
        } else {
            if (turn_A) {
                a_str += to_string(half + 1);
                b_str += to_string(half);
            } else {
                a_str += to_string(half);
                b_str += to_string(half + 1);
            }
            turn_A = !turn_A;
        }
    }

    // 使用stoll来处理可能的大数，并去除前导零
    cout << stoll(a_str) << " " << stoll(b_str) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            String nStr = sc.next();
            StringBuilder aStr = new StringBuilder();
            StringBuilder bStr = new StringBuilder();
            boolean turnA = true;

            for (char c : nStr.toCharArray()) {
                int digit = c - '0';
                int half = digit / 2;
                if (digit % 2 == 0) {
                    aStr.append(half);
                    bStr.append(half);
                } else {
                    if (turnA) {
                        aStr.append(half + 1);
                        bStr.append(half);
                    } else {
                        aStr.append(half);
                        bStr.append(half + 1);
                    }
                    turnA = !turnA;
                }
            }
            // 使用 Long.parseLong 来处理大数并去除前导零
            System.out.println(Long.parseLong(aStr.toString()) + " " + Long.parseLong(bStr.toString()));
        }
    }
}

import sys

def solve():
    n_str = sys.stdin.readline().strip()
    a_str = []
    b_str = []
    turn_A = True

    for char_digit in n_str:
        digit = int(char_digit)
        half = digit // 2
        if digit % 2 == 0:
            a_str.append(str(half))
            b_str.append(str(half))
        else:
            if turn_A:
                a_str.append(str(half + 1))
                b_str.append(str(half))
            else:
                a_str.append(str(half))
                b_str.append(str(half + 1))
            turn_A = not turn_A
    
    # 使用 int() 来处理大数并去除前导零
    print(int("".join(a_str)), int("".join(b_str)))


def main():
    t_str = sys.stdin.readline()
    if not t_str: return
    t = int(t_str)
    for _ in range(t):
        solve()

main()

算法及复杂度

  • 算法: 构造、贪心
  • 时间复杂度: 我们需要遍历一遍输入数字 的每一位。设 的位数为 ，则单次操作的时间复杂度为 。总时间复杂度为 。
  • 空间复杂度: 我们需要额外的字符串来构造 和 ，其长度与 的位数成正比，因此空间复杂度为 。