题目大意
在使用奶牛最少的情况下求出需要多少头牛
考纲知识点
输入输出、分支结构、循环结构、算术运算符、一维数组、sortsortsort 排序、自定义函数、贪心算法、基础数据类型、变量的定义以及使用
解题思路
要想使奶牛的数量少又能到达书架的顶端,需要使用贪心算法使牛的高度最大
排序数组 a[i]a[i]a[i] ,从大到小排序
循环遍历从 111 开始,因为之前已经排序,现在的 a1a_1a1 是最大的奶牛高度,后面是依次减少但其次高的奶牛
每次都加上目前看来最大的,用 sumsumsum 变量记录下目前奶牛叠加在一起的高度,用 cntcntcnt 变量记录下目前奶牛的数量,如果 sumsumsum 大于书架的高度 bbb 就说明奶牛的高度已经够了,结束循环
参考程序
时间复杂度
O(nlogn)O(n log n)O(nlogn)(线性对数时间复杂度)
空间复杂度
O(n)O(n)O(n)(线性空间复杂度)