思路：模拟

一个很直观的贪心想法，按攻击力从小到大依次考虑攻击每个怪兽，在攻击成功后，增加金币，则更新答案。然后继续考虑攻击下一个怪兽，直到无法攻击成功或者没有怪兽可以攻击，则结束。

时间复杂度：$O(n\log n)$ ，排序的时间复杂度。

python

start, n = map(int, input().split())
a = list(map(int, input().split()))

题目描述

塔子哥在玩一款打怪游戏。游戏里有 $n$ 个怪兽，第 $i$ 个怪兽的攻击力为 $a_i$ 。

塔子哥可以按照自己的想法选择任意 $k(0\leq k\leq n)$ 个怪兽进行战斗，并可以以任意和这 $k$ 个怪兽依次战斗。现在塔子哥面对他要打的第 $i$ 个怪兽时，其攻击力为 $b$ ，

• 当 $b \geq a_i$ ，则他可以战胜这个怪兽，并获得一枚金币，一枚金币可以让塔子哥的攻击力增加 $1$ 点。
• 当 $b < a_i$ ，则塔子哥被击败，不可以再打后面的怪兽。

初始塔子哥手里没有金币，攻击力为 $start$ ，现在你需要告诉塔子哥，最优情况下，他可以获得最多的金币数是多少。

输入描述

第一行，两个正整数 $start,n(1\leq start,n\leq 10^5)$ ，分别代表塔子哥的初始攻击力和怪兽的总数量。
接下来一行，$n$ 个正整数 $a$ ，第 $i$ 个数 $a_i(1\leq a_i\leq 10^5)$ 表示第 $i$ 个怪兽的攻击力。

输出描述

一个整数，表示最优情况下，塔子哥可以获得最多的金币数。

样例

输入

3 5
5 4 3 4 5

输出

3

说明

击败能力值为 $3$ 的怪兽，获得 $1$ 枚金币，提升攻击力 $1$ 点，攻击力为 $4$ 。
击败了两只攻击力为 $4$ 的怪兽，获得 $2$ 枚金币，提升攻击力 $1$ 点，攻击力为 $5$ 。
击败两只攻击力为 $5$ 的怪兽，获得 $2$ 枚金币 。

金币数最多为 $3$ 。