题解：P2676 [USACO07DEC] Bookshelf B

Yxa_Sheep · 2025-08-10 22:31:28 · 题解

题目传送门

题意

有 n 头奶牛和书柜高度 b，给定他们的身高 h_i，求最少需要多少头奶牛可以达到高度 b。

思路

我们可以想到贪心，尽量使用高的奶牛。先将奶牛高度从高到低排序，可以这样写 sort(a + 1, a + n + 1, greater<int>());。再一个一个取，用 sum 记录当前高度，直到高度大于等于 b 为止。

代码

#include <bits/stdc++.h>
using namespace std;
int n, b, sum, a[20010];
int main()
{
    scanf("%d%d", &n, &b);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1, greater<int>());
    for (int i = 1; i <= n; i++)
    {
        sum += a[i];
        if (sum >= b)
        {
            printf("%d", i);
            break;
        }
    }
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门