把 x 看成十进制数位序列 d0d1…dn−1(从高位到低位),数位和为 S。要找 y<x 且数位和仍为 S。
一种稳定构造:在某个位置 i(0≤i≤n−2)把 di 减 1(要求 di≥1),再把后缀 i+1,…,n−1 重新分配,使后缀数位和增加 1。整体和不变,且第 i 位变小,必有 y<x。
记原后缀和为 R,新后缀目标和为 R+1,后缀长度为 L=n−i−1。只要 R+1≤9L 就能把和 R+1 分配到 L 个 [0,9] 的数位中。R≤9L 恒成立,上式不成立当且仅当后缀全为 9。因此只需找到位置 i 满足:
给定一个非负整数 x(可能非常大,以十进制字符串给出)。请构造一个非负整数 y,满足 y<x,且 x 与 y 的十进制数位之和相等。
若存在满足条件的 y,输出任意一个即可;否则输出 -1。
数据范围:x 的十进制位数不超过 105,且 0≤x。
输入一行,包含一个整数 x(0≤x,位数不超过 105),以十进制字符串形式给出,可能含前导零。
开通会员即可查看完整视频题解: 1.题目讲解 2.思路分析 3.逐行代码手写
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册