AI 生成摘要
该问题要求在预算 $B$ 内购买尽可能多的房子，核心思路是优先购买低价房子。具体步骤包括：先将房价数组从小到大排序，然后从头依次累加价格，直到总价超过预算为止，此时累加的数量即为答案。该方法属于贪心算法结合排序，时间复杂度为 $O(N \log N)$，空间复杂度为 $O(N)$。

思路

要想在预算 B 下买到尽可能多的房子，显然应当优先买价格低的房子。

  1. 对房价数组进行从小到大排序；
  2. 从头累加每套房子的价格，直到总价超过 B 为止；
  3. 累加的房子数量即为答案。

这种方法是典型的“贪心＋排序”

复杂度分析

  • 排序：$O(N log N)$
  • 累加：$O(N)$
  • 单次处理时间：$O(N log N)$，空间 $O(N)$，可满足题目要求。

然后直接看代码吧

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T, n, b, a[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	for (int t = 1; t <= T; t++)
	{
		cin >> n >> b;
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		sort(a + 1, a + n + 1);
		int sum = 0, ans = 0;
		for (int i = 1; i <= n; i++)
		{
			if (sum + a[i] <= b)
				sum += a[i], ans++;
			else
				break;
		}
		printf("Case #%d: %d\n", t, ans);
	}
}