题意:
当一个整数高位数字总不小于低位数字,或者说写成字符串之后单调不下降,称之为上升数。求一个整数最少能表示为多少个上升数的和。(n<=1e500000)
分析:
考虑那些不下降的数字,一定可以写成9个1111...,1111...,11...,0这样的和,每个数可以表示成(10^r-1)/9
我们现在不求最小的k,来改成判定问题,判定n能否写成k个上升数的和
k个上升数对应了9k个(10^ri-1)/9
也就是n=Σ(10^ri-1)/9 (1<=i<=9k)
化简一下就是9n+9k=Σ(10^ri) (1<=i<=9k)
我们可以计算出9n+9k的位数,如果这个位数<=9k,那么就可以构造出这样的ri,使得k满足
时间复杂度O(lenloglen)