简答题 偏难
#7218

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

书架

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">#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>
这道题暂未补解析。