U567795 allocation 题解

思路

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