“眼淚不是我們的答案，拼搏才是我們的選擇。”

題目描述

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個整數，即最少要多少頭奶牛疊成塔，才能夠到書架頂部輸入輸出樣例

輸入 #1複製

6 4061811131911

輸出 #1複製

3

說明/提示

輸入說明:

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

輸出說明:

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

這條題其實很簡單，問最少需要多少頭牛疊加後的身高和可以達到書架的高度？，我們將牛的身高進行從大到小的排序，取最大的幾個疊加，則所需要的牛的個數最少。

我們使用兩種方法來編寫程式。

法一：快速排序演算法：

#include<iostream>using namespace std;int  high[20005];void qsort(int high[],int l,int r){	int i=l,j=r,flag=high[(l+r)/2],tmp;	do{		while(high[i]<flag) i++;		while(high[j]>flag) j--;		if(i<=j){			tmp=high[i];high[i]=high[j];high[j]=tmp;			i++;j--;		}	}while(i<=j);	if(l<j) qsort(high,l,j);	if(i<r) qsort(high,i,r);}int main(){	int n,b,sum=0,count=0;	cin>>n>>b;	for(int i=1;i<=n;i++){		cin>>high[i];	}	qsort(high,1,n);	for(int i=n;sum<=b;i--){		sum+=high[i];		count++;	}	cout<<count;	return 0;}

法二：sort一鍵排序演算法：

#include<iostream>#include<algorithm>using namespace std;int high[20005];bool cmp(int a,int b)//使用sort排序定義從大到小{	return a>b;}int main(){	int n,b;	cin>>n>>b;	for(int i=0;i<n;i++)	{		cin>>high[i];	}	sort(high,high+n,cmp);//sort一鍵排序	int sum=0,ans=0;	while(sum<b)//只要高度不夠就繼續疊	{		sum+=high[ans];		ans++;	}	cout<<ans;	return 0;}

注意呼叫sort需要新增標頭檔案#include<algorithm> 哦。