首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7470

书架(2023.12) John最近买了一个书架用来存放奶牛养殖书籍,但书架很快被存满了,只剩最顶层有空余。 John共有N头奶牛(1 ≤ N ≤ 20,000…

书架(2023.12)

John最近买了一个书架用来存放奶牛养殖书籍,但书架很快被存满了,只剩最顶层有空余。

John共有N头奶牛(1 ≤ N ≤ 20,000),每头奶牛有自己的高度Hi(1 ≤ Hi ≤ 10,000),N头奶牛的总高度为S。书架高度为B(1 ≤ B ≤ S < 2,000,000,007).

为了到达书架顶层,奶牛可以踩着其他奶牛的背,像叠罗汉一样,直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层,找出使用奶牛数目最少的解决方案吧。

时间限制:10000

内存限制:65536

输入

第1行:空格隔开的整数N和B 第2~N+1行:第i+1行为整数Hi

输出

能达到书架高度所使用奶牛的最少数目


样例输入

6 40
6
18
11
13
19
11

样例输出

3
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">// 参考代码1 #include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #define INF 999999999 #define N 20001 using namespace std; int a[N]; void qsort(int x, int y) {   int i = x, j = y, mid = a[(x + y) / 2];   while (i &lt;= j) {     while (a[i] &gt; mid)       i++;     while (a[j] &lt; mid)       j--;     if (i &lt;= j) {       swap(a[i], a[j]);       i++;       j--;     }   }   if (x &lt; j)     qsort(x, j);   if (i &lt; y)     qsort(i, y); } int main() {   int n, b;   int sum = 0;   int i;   cin &gt;&gt; n &gt;&gt; b;   for (i = 1; i &lt;= n; i++)     cin &gt;&gt; a[i];   qsort(1, n);   for (i = 1; i &lt;= n; i++) {     sum += a[i];     if (sum &gt;= b)       break;   }   cout &lt;&lt; i &lt;&lt; endl;   ;   return 0; }</pre><pre class="brush:cpp;toolbar:false">// 参考代码2 #include &lt;bits/stdc++.h&gt; using namespace std; int n, b, a[20002]; int main() {   cin &gt;&gt; n &gt;&gt; b;   for (int i = 0; i &lt; n; i++)     cin &gt;&gt; a[i];   sort(a, a + n);   long long s = 0;   for (int i = n - 1; i &gt;= 0; i--) {     s += a[i];     if (s &gt;= b) {       cout &lt;&lt; n - i &lt;&lt; endl;       return 0;     }   }   return 0; }</pre>
这道题暂未补解析。