【AtCoder Grand 011E】Increasing Numbers 题解

题目大意

  如果一个数，从高位到低位是递增的，则称为上升数，例如 1122345。
  现在有个大整数 $n$，求至少需要多少个上升数，使它们的和为 $n$。
  $n \le 10^{5 \times 10^5}$

解法1.1

  上升数可以拆成很多个形如 1111...111 的全 1 数，例如 1122345=1111111+11111+111+11+1。
  所以可以考虑把 $n$ 拆成全 1 数，然后合并。因为 1 个上升数最多由 9 个全 1 数合并而来，并且可以任意组合，所以最后的答案是 $\lceil \frac{全1数的数量}{9} \rceil$，因此最小化全 1 数的数量即可。

  然后全 1 数可以看成是 1+10+100+100……这样的等比数列和，因此一个 $n$ 位的全 1 数等于 $\frac{10^n-1}{9}$。假设我们最后拆成的全 1 数有 $k$ 个，位数分别是 $a[1]...a[k]$，则有 $\sum_{i=1}^{k}(10^{a[i]}-1)=9n$，我们要最小化 $k$。

  枚举这个 $k$ 就行了，因为判断条件是 $9n+k$ 的数位和等于 $k$，所以$k$ 是 $O(5e5)$ 的。

解法1.2

  事实上这个 $k$ 不需要枚举，因为 $9n+k$ 的数位和的增长速度比 $k$ 慢，所以二分 $k$ 就行了。

解法2

  上述拆成全 1 数的方法其实证明了贪心是对的，即每次选最大的全 1 数，或者回到原题是每次选最大的上升数。比如 720464=699999+20465=699999+19999+466

  因为 $n-a=n-(a+1)+1$，所以每次分离一个最大的上升数就相当于，从最高位开始找最长连续的上升序列，然后删掉这个序列，剩下的这个数+1。

  所以就 $O(5e5)$ 地从高位开始扫。高精度+1的复杂度也是 $O(5e5)$。（每 10 次加法会用到第二位、每 100 次加法会用到第三位……所以是 $5e5+\frac{5e5}{10}+\frac{5e5}{100}+……$）