题解 | #数位差与数值和的构造#

数位差与数值和的构造

https://www.nowcoder.com/practice/36f3593e553c4c67987abf88a3d4d105

题目链接

数位差与数值和的构造

题目描述

给定一个整数 ,请找到两个非负整数 ,满足以下两个条件:

  1. 的数字和与 的数字和之差的绝对值不超过 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()

算法及复杂度

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

相关推荐

头像
04-27 15:11
已编辑
华东师范大学 算法工程师
暑期实习从2月开始投,面了两个月,流程该挂的都挂完了,腾讯字节一共号称是1.7w个hc,不知道都发给谁了,估计今年秋招要难顶。Timeline米哈游、美团、蚂蚁、微软等公司直接简历挂穿,没进面。携程:3.3&nbsp;投递、测评3.12&nbsp;笔试3.18&nbsp;一面3.25&nbsp;二面4.13&nbsp;ai面(hr面)4.14&nbsp;英语测评4.23&nbsp;offer(已拒)腾讯:2.6&nbsp;测评2.28&nbsp;wxg一面3.5&nbsp;wxg二面(挂)3.11&nbsp;teg一面3.21&nbsp;teg二面(取消)3.31&nbsp;teg一面4.10&nbsp;teg二面(挂)4.21&nbsp;wxg一面4.24&nbsp;wxg二面(挂)字节:1.28&nbsp;aml约面(取消)3.17&nbsp;火山一面(挂)4.8&nbsp;aml一面(挂)4.20&nbsp;抖音data一面(挂)阿里:3.23&nbsp;投递、测评3.28&nbsp;笔试3.31&nbsp;淘天一面4.8&nbsp;钉钉一面4.9&nbsp;淘天二面4.10&nbsp;阿里控股一面4.12&nbsp;钉钉二面(取消)4.15&nbsp;淘天hr面4.16&nbsp;淘天offer(已接)4.21&nbsp;高德一面(取消)4.22&nbsp;淘宝闪购一面(取消)面试最大的感触是,现在撞上ai转型,一堆老业务急着转向,新业务非常不成熟,研究型的组bar非常高根本进不去,业务侧挂着算法的岗位干的都是工程活,面试却又要问算法,另外agent的落地也远没有那么广,绝大多数还是那套写死的系统调一下llm&nbsp;api或者做做rag,其余少部分真的在搭agent的,基本不能在线上服务用什么很智能的模型,现阶段成本太高,进去大概率就是给垃圾模型从工程方面兜底,除了业务场景的应用和数据经验以外,技术方面很难有什么提升。算法岗做不了基模的还是去搜广推好,之前判断失误了完全没投,秋招不知道还进不进得去。
绿糖滑稽:携程这什么雷霆流程时长
我的求职进度条
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务