高质量题解|书架

题目大意

在使用奶牛最少的情况下求出需要多少头牛

考纲知识点

输入输出、分支结构、循环结构、算术运算符、一维数组、$sort$ 排序、自定义函数、贪心算法、基础数据类型、变量的定义以及使用

解题思路

要想使奶牛的数量少又能到达书架的顶端，需要使用贪心算法使牛的高度最大
排序数组 $a[i]$ ，从大到小排序
循环遍历从 $1$ 开始，因为之前已经排序，现在的 $a_1$ 是最大的奶牛高度，后面是依次减少但其次高的奶牛
每次都加上目前看来最大的，用 $sum$ 变量记录下目前奶牛叠加在一起的高度，用 $cnt$ 变量记录下目前奶牛的数量，如果 $sum$ 大于书架的高度 $b$ 就说明奶牛的高度已经够了，结束循环

参考程序

#include <bits/stdc++.h>
using namespace std;
int a[20010];
//从大到小排序 定义规则 
bool cmp(int x,int y){
	return x > y;
}
int main(){
	int n,b;
	cin >> n >> b;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	//从大到小排序n个奶牛的身高
	sort(a + 1,a + n + 1,cmp); 
	int sum = 0,cnt = 0;//定义奶牛的总高度和数量 
	for(int i = 1;i <= n;i++){
		sum += a[i];
		cnt++;
		if(sum >= b){
			break;
		} 
	} 
	cout << cnt;
	return 0;
}

时间复杂度

$O(n log n)$(线性对数时间复杂度)

空间复杂度

$O(n)$(线性空间复杂度)