F2. Nearest Beautiful Number (hard version) (贪心)

注意到一个结论：答案和

n

n同位数，因为当所有位都为

9

9必定满足。

然后就可以贪心，找到满足不同位数

≤

k

\le k

≤k的最大前缀

+

1

+1的位置，显然此位需要加1，后面的位全部修改为

0，然后修改

n，直到

n满足条件为止。

e

p

:

=

4561

,

3

ep: n=4561,k=3

ep:n=4561,k=3

最大前缀是

456

456，需要对

1加不断

1，直到

4564

n=4564

n=4564满足情况返回。

4512

2

ep:n=4512,k=2

ep:n=4512,k=2。

最大前缀

45

45，第三位的

1加

1，后面置为

0，

4520

n=4520

n=4520，然后再重新模拟。

→

4530

4540

4544

n\rightarrow 4530\rightarrow 4540\rightarrow 4544

n→4530→4540→4544。

设

n的位数是

m

m位。

每位最多修改

10

10次，每次遍历最多

m位，最多遍历

m次。

时间复杂度：

O

(

)

O(10m^2)

O(10m2)