AI 生成摘要
本文章介绍了解决在预算 `B` 下购买最多房子的算法问题。使用贪心策略，先对房价从小到大排序，然后从低价开始累加直到超出预算，累加数量即为答案。算法时间复杂度为 O(N log N)，主要由排序步骤决定。C++代码示例实现了该逻辑，直接处理输入输出。

思路

要想在预算 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);
	}
}