题解原作者：2017级吴昊钟 NOI2019铜牌

难度：普及+/提高

算法一：暴力枚举

在 $[ 0,n ]$ 的范围内暴力枚举 $m$ 的取值，直接统计 $[m,n]$ 之间的数中 $0$ 出现的次数为 $k$ 的最大 $m$ 的值。

时间复杂度：$O(N^2)$

期望得分：$30$分

算法二：前缀和+扫描法

在 $[0,n]$ 的范围内扫描，每一次进位使用类似高精度加法的方式维护 $0$ 出现的次数的变化情况，选取 $sum(n)-sum(m-1)$ 的值为 $k$ 的最大 $m$ 的值。

时间复杂度：$O(N)$

期望得分：$50$分

算法三：前缀和+组合计数

利用加法原理和乘法原理可以直接计算出 $f(n)$ 为 $[0,n]$ 之间的数中 $0$ 出现的次数，从 $n$ 开始倒序扫描选取第一个 $sum(n)-sum(m-1)$ 的值为 $k$ 的 $m$ 即可。也可以将算法二倒序维护解决。

时间复杂度：$O(N-M)$

期望得分：$70$分

算法四：二分法+前缀和+组合计数

在前一个算法的基础上利用二分法快速索引满足条件的 $m$ 的最大值即可。

时间复杂度：$O(log_{2}N)$

期望得分：$100$分