1228：書架

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 7573 ??? 通過數: 4313

【題目描述】

John最近買了一個書架用來存放奶牛養殖書籍，但書架很快被存滿了，只剩最頂層有空余。

John共有N頭奶牛(1≤N≤20,000)，每頭奶牛有自己的高度Hi(1≤Hi≤10,000)，N頭奶牛的總高度為S。書架高度為B(1≤B≤S<2,000,000,007)。

為了到達書架頂層，奶牛可以踩著其他奶牛的背，像疊羅漢一樣，直到他們的總高度不低于書架高度。當然若奶牛越多則危險性越大。為了幫助John到達書架頂層，找出使用奶牛數目最少的解決方案吧。

【輸入】

第1行：空格隔開的整數N和B。

第2~N+1行：第i+1行為整數Hi。

【輸出】

能達到書架高度所使用奶牛的最少數目。

【輸入樣例】

6 40 6 18 11 13 19 11

【輸出樣例】

3

【分析】

? ? ? ? 本題的貪心策略是奶牛高的先用于疊羅漢。所以，需要先對牛的高度進行排序，然后從高到低選奶牛，直到到達書架的高度。

【參考代碼】

#include <stdio.h> #define N 20010 int a[N]; //奶牛高度數組 int main() {int i,j,n,b,s=0,t;scanf("%d%d",&n,&b);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n-1;i++) //比較排序 {for(j=i+1;j<n;j++){if(a[i]<a[j]){t=a[i];a[i]=a[j];a[j]=t;}}}for(i=0;i<n;i++){s+=a[i];if(s>=b)break;}printf("%d\n",i+1);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1228

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1228：书架）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。