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)