1181B - Split a Number（源地址自⇔CF1181B）

• 1181B - Split a Number（源地址自⇔CF1181B）
  • tag
  • 题意
  • 思路
  • AC代码
    • 错误次数

tag

⇔贪心、⇔构造性算法、⇔字符串、⇔高精度、⇔其他编程语言、⇔提高级（*1500）

题意

给出一串长度位数在 \(1\) 到 \(10^5\) 的数字，要求将其分为不含前导零的两串，使得这两串之和最小。

思路

首先避不开的是高精度的问题，故我们使用 \(\tt{Python}\) 来解决这道题。

第一反应便是遍历一遍每一个位置，判断其是否可能，并记录。然而，不幸的是，这会导致超时——由于对于每一个位置都要进行一次加法运算，时间复杂度为 \(\mathcal{O}(n ^ 2)\) 。我们再考虑优化：两串的长度尽可能的相近，它们的和越小。故只需要从中间开始，向两侧遍历到第一个、使得两个串都不含前导零的位置，计算比较这两个位置的答案即可，此方法的时间复杂度至多为 \(\mathcal{O} (n)\) 。

需要指出的是， \(\tt{Python}\) 的整除是两个斜杠 \(//\) （注意： \(\tt{Python}\) 的浮点数精度与 \(\tt{C++}\) 一致，均为 \(14 - 16\) 位，如先使用除法再强制转换为 \(\tt{int}\) 型，会导致先计算成浮点数而损失精度）， \(\tt{for}\) 循环是小开大闭。

AC代码

#A WIDA Project
n = int(input())
s = input()
mid = n // 2
ans = int(s)
for i in range(mid, 0, -1):
    if s[i] == '0':
        continue
    else:
        ans = min(ans, int(s[:i]) + int(s[i:]))
        break

for i in range(mid + 1, n):
    if s[i] == '0':
        continue
    else:
        ans = min(ans, int(s[:i]) + int(s[i:]))
        break
print(ans)

错误次数

【补题 2 次】没有使用整除，导致浮点数溢出精度出错。

【补题 2 次】直接遍历，导致超时。

【补题 1 次】忘记添加前导零的判断条件。

【补题 1 次】未注意倒序 \(\tt{for}\) 循环的区间条件，导致少计算了一位。

文 / WIDA
2022.01.17 成文
首发于WIDA个人博客，仅供学习讨论

更新日记：
2022.01.17 成文