玩具购买（Maximum Toys）

题目描述

Mark 和 Jane 在迎来他们的第一个孩子后非常开心。

他们的儿子喜欢玩具，因此 Mark 想买一些玩具送给他。

现在有 n 个不同的玩具摆在 Mark 面前，每个玩具都有一个价格。

Mark 手里有一定数量的钱，他希望在预算范围内购买尽可能多的玩具。

给定每个玩具的价格数组 prices 和 Mark 的预算 k，请计算 Mark 最多可以买多少个玩具。

注意：

• 每个玩具最多购买一次。

---

输入格式

第一行包含两个整数：

n k

其中：

• n 表示玩具的数量；
• k 表示 Mark 可用于购买玩具的钱数。

第二行包含 n 个整数：

prices[1] prices[2] ... prices[n]

表示每个玩具的价格。

---

输出格式

输出一个整数：

表示 Mark 最多可以买到的玩具数量。

---

数据范围

1 ≤ n ≤ 10^5

1 ≤ k ≤ 10^9

1 ≤ prices[i] ≤ 10^9

保证：

每个玩具只能购买一次。

---

样例 1

输入

4 7
1 2 3 4

输出

3

解释

预算为：

k = 7

玩具价格：

[1,2,3,4]

可以买：

方案1：

1 + 2 + 3 = 6

购买 3 个玩具。

方案2：

3 + 4 = 7

购买 2 个玩具。

因此最多购买：

3 个玩具

---

样例 2

输入

7 50
1 12 5 111 200 1000 10

输出

4

解释

预算：

50

玩具价格：

1 12 5 111 200 1000 10

选择：

1 + 5 + 10 + 12 = 28

可以买到：

4 个玩具

继续增加任何一个玩具都会超过预算。

所以答案为：

4

---

手动模拟

例如：

prices:

7 3 5 2 10

k = 15

排序：

2 3 5 7 10

购买：

玩具价格	累计花费	购买数量
2		1
3	5	2
5	10	3
7	17	超过预算

停止。

答案：

3

---

算法复杂度

排序：

O(n log n)

遍历：

O(n)

总复杂度：

O(n log n)

空间复杂度：

O(1)

（不考虑排序空间）

贪心口诀

想买最多件，先买最便宜； 排序从小到大，能买继续买。