洛谷P2676 超級書架

題目描述

Farmer John最近為奶牛們的圖書館添置了一個巨大的書架，儘管它是如此的大，但它還是幾乎瞬間就被各種各樣的書塞滿了。現在，只有書架的頂上還留有一點空間。 所有N(1 <= N <= 20,000)頭奶牛都有一個確定的身高H_i(1 <= H_i <= 10,000)。設所有奶牛身高的和為S。書架的高度為B，並且保證 1 <= B <= S < 2,000,000,007。 為了夠到比最高的那頭奶牛還要高的書架頂，奶牛們不得不象演雜技一般，一頭站在另一頭的背上，疊成一座“奶牛塔”。當然，這個塔的高度，就是塔中所有奶牛的身高之和。為了往書架頂上放東西，所有奶牛的身高和必須不小於書架的高度。顯然，塔中的奶牛數目越多，整座塔就越不穩定，於是奶牛們希望在能夠到書架頂的前提下，讓塔中奶牛的數目儘量少。 現在，奶牛們找到了你，希望你幫她們計算這個最小的數目。

輸入輸出格式

輸入格式：

• 第1行: 2個用空格隔開的整數：N 和 B * 第2..N+1行: 第i+1行是1個整數：H_i

輸出格式：

• 第1行: 輸出1個整數，即最少要多少頭奶牛疊成塔，才能夠到書架頂部

輸入輸出樣例

6 40
6
18
11
13
19
11

3

說明

輸入說明:

一共有6頭奶牛，書架的高度為40，奶牛們的身高在6..19之間。

輸出說明:

一種只用3頭奶牛就達到高度40的方法：18+11+13。當然還有其他方法，在此不一一列出了。

貪心

排個序，從大的開始枚舉，滿足條件就退出

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define ls k<<1
 7 #define rs k<<1|1
 8 using namespace std;
 9 const int MAXN=400400;
10 inline void read(int &n)
11 {
12     char c=getchar();n=0;bool flag=0;
13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
15 }
16 int n,h;
17 int a[MAXN];
18 int main()
19 {
20     read(n);read(h);
21     for(int i=1;i<=n;i++)    read(a[i]);
22     sort(a+1,a+n+1);
23     int now=0;
24     for(int i=n;i>=1;i--)
25     {
26         now+=a[i];
27         if(now>=h)    {    printf("%d",n-i+1);    exit(0);    }
28     }
29     return 0;
30 }