1216 书架
大约 3 分钟贪心
1216 书架
【算法标签】 贪心
【语法标签】 :数组、sort、自定义比较函数(cmp)、for循环
John 有 头奶牛(),每头奶牛有一个高度 (),所有奶牛高度之和为 。书架的高度为 ()。
奶牛们可以玩"叠罗汉"——一头站在另一头上面,使总高度增加。问:至少需要多少头奶牛,才能使叠起来的总高度达到或超过书架高度 ?
换句话说:给定一个整数 和一堆高度 ,选出数量最少的 ,使得它们的和 。
输入格式:
- 第 1 行:两个整数 和
- 第 2 ~ 行:每行一个整数
输出格式:
- 一个整数,表示最少需要多少头奶牛
样例:
输入:
6 40
6
18
11
13
19
11
输出:
3解释:选高度 19、18、11,总和 ,用了 3 头奶牛。
二、解题思路
数据规模分析
- , 的排序完全可以接受。
- ,总高度 不超过 ,用
int可能会溢出某次累加(题目说 ,实际上int上限约 ,刚好够但要小心),我们直接用long long或保持用int即可(本题 确实在int范围内,但稳妥起见用long long)。
算法选择:贪心
问题本质是:从一堆数中选最少的数,让它们的和 。
直觉:为了让数量最少,当然要优先选最高的奶牛。每一头最高的奶牛贡献最大,能最快把总高度堆到 。
这就是贪心策略:每次选当前最高的奶牛,累加直到总高度 。
为什么贪心是对的?反证法:假设最优解没有选最高的那头奶牛 ,把它替换掉最优解中某头较矮的奶牛,总高度只会增加不会减少,而且数量不变。因此选最高的不会比最优解差。
算法流程
- 读入 和
- 读入 个 存入数组
- 将数组从大到小排序
- 从大到小依次累加,每加一个计数器 +1
- 当累加和 时,输出计数器并结束
手动模拟样例
,高度:
- 从大到小排序:
- 累加:
- 取 19,总和 = 19,计数 = 1(19 < 40,继续)
- 取 18,总和 = 37,计数 = 2(37 < 40,继续)
- 取 13,总和 = 50,计数 = 3(50 40,停止)
- 输出 3
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 20005;
int h[N]; // 奶牛高度
// 从大到小排序的比较函数
bool cmp(int a, int b) {
return a > b;
}
int main() {
int n, b;
cin >> n >> b;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
// 从大到小排序
sort(h + 1, h + n + 1, cmp);
int sum = 0; // 当前叠起来的总高度
int ans = 0; // 使用的奶牛数量
for (int i = 1; i <= n; i++) {
sum += h[i];
ans++;
if (sum >= b) { // 达到书架高度
break;
}
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。排序占主导,,完全可以接受。
- 空间复杂度:。需要一个长度为 的数组存储奶牛高度。
易错点:排序方向不要搞反。本题要从大到小排(优先选高的),所以 cmp 应该返回 a > b,或者用 STL 的 greater<int>()。
