AI 生成摘要
该问题在给定预算下求最大可购房屋数，应采用贪心算法：先将房价数组从小到大排序，然后从头依次累加购买，直到总价超出预算停止。此方法时间复杂度为 $O(N \log N)$，空间复杂度为 $O(N)$，能有效解决问题。代码示例展示了排序、累加及判定逻辑的完整实现。
思路
要想在预算 B 下买到尽可能多的房子，显然应当优先买价格低的房子。
- 对房价数组进行从小到大排序；
- 从头累加每套房子的价格，直到总价超过
B为止； - 累加的房子数量即为答案。
这种方法是典型的“贪心＋排序”
复杂度分析
- 排序：$O(N log N)$
- 累加：$O(N)$
- 单次处理时间：$O(N log N)$，空间 $O(N)$，可满足题目要求。
然后直接看代码吧
AC 代码
#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);
}
}