P4637 书架（基础）

解题思路

这道题是经典的贪心问题：把奶牛叠成「奶牛塔」，总身高达到或超过书架高度 B 就够到了，问最少用几头奶牛。

**第一步，读懂题意。**每头奶牛有一个身高，把所有选中的奶牛身高加起来，只要总和不小于书架高度 shelfHeight 就成功。希望用的奶牛数量越少越好。

**第二步，想清楚贪心策略。**既然要用的奶牛越少越好，当然要优先选最高的奶牛。最高的奶牛一头顶好几头矮的，选它能更快凑够高度。比如一头 1.9 米和一头 1.1 米的奶牛，目标高度 3 米：选 1.9 米的两头就够，而选 1.1 米的可能要多选好几头。所以策略就是：从最高的奶牛开始，一头一头往下选，直到总身高不小于 shelfHeight。

**第三步，用计数数组代替排序。**奶牛身高范围是 1 到 10000，范围很小，所以可以用计数数组 heightCount[height] 记录每种身高的奶牛有几头，然后从最高身高 10000 往下检查，完全不用写复杂的排序。

**第四步，把同身高的奶牛打包计算。**当还差 shelfHeight - totalHeight 的高度时，最少还需要几头身高为 height 的奶牛？答案是 (还差高度 + height - 1) / height，这个「加 height 减 1 再整除」的式子实现了向上取整。当然取的数目不能超过这种身高的实际数量 heightCount[height]，所以要和它取较小值。

**第五步，注意用 long long。**所有奶牛身高总和可以接近 2,000,000,000，已经逼近 int 的上限，累加时用 long long 更安全，不会溢出。

**第六步，确认边界。**题目保证所有奶牛身高之和不小于 shelfHeight，所以一定能找到答案，不用考虑「够不到」的情况。

参考代码

// 用身高计数，从最高的奶牛开始选择，求达到书架高度的最少数量。
#include <iostream>
using namespace std;

int main() {
    int n; // 奶牛总数。
    long long shelfHeight; // 书架高度。
    long long heightCount[10001] = {0}; // heightCount[height]表示身高为height的奶牛数量。
    int i; // 读入循环变量。
    cin >> n >> shelfHeight; // 读入奶牛数量和书架高度。
    for (i = 0; i < n; i++) { // 读入每头奶牛的身高。
        int height; // 当前奶牛的身高。
        cin >> height; // 读入身高。
        heightCount[height]++; // 记录这种身高的奶牛数量。
    }
    long long totalHeight = 0; // 已选奶牛的身高总和。
    long long cowCount = 0; // 已选奶牛的数量。
    int height; // 从高到低检查的身高。
    for (height = 10000; height >= 1 && totalHeight < shelfHeight; height--) { // 优先选择更高的奶牛。
        if (heightCount[height] == 0) continue; // 这种身高没有奶牛就跳过。
        long long takeCount = (shelfHeight - totalHeight + height - 1) / height; // 还差的高度至少需要几头这种奶牛。
        if (takeCount > heightCount[height]) takeCount = heightCount[height]; // 不能选超过实际拥有的数量。
        totalHeight += takeCount * height; // 加上选中奶牛的总身高。
        cowCount += takeCount; // 加上选中奶牛的数量。
    }
    cout << cowCount << '\n'; // 输出最少奶牛数量。
    return 0; // 程序正常结束。
}

复杂度分析

时间上，读入 n 头奶牛需要 O(n) 时间；从身高 10000 向下检查最多循环 10000 次，是常数时间。所以总时间复杂度是 O(n)。空间上，使用了一个大小固定的计数数组 heightCount[10001]，空间复杂度是 O(1)。n 最大为 20000，这个算法可以瞬间完成。相比排序后逐头累加的方法，利用身高范围小的特点用计数法，效率更高且代码更简洁。