传送门：P2676 [USACO07DEC] Bookshelf B

更佳的阅读体验：洛谷 P2676 题解

简要题意：给定一个有 $n$ 个元素的序列 $h$，求最小的子集大小，使得子集中元素之和不小于 $b$。

题目没有要求我们凑出的奶牛身高之和恰好等于 $b$，而是只要不小于 $b$ 即可，因此我们可以考虑贪心：贪心地选择更高的奶牛一定是正确的。

我们对整个数组从大到小排序，然后对每个位置 $i$ 计算前缀和。前缀和第一个不小于 $b$ 的元素的下标即为答案。

记得开 long long。

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

const int N = 2e4 + 10;
int n, b;
ll h[N];

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> b;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    sort(h + 1, h + n + 1, greater<>());
    for (int i = 1; i <= n; ++i) {
        h[i] += h[i - 1];
        if (h[i] >= b) {
            cout << i << '\n';
            return 0;
        }
    } return 0;
}