魔法学院放暑假了，WC和他的一帮魔友一起去弗尔夫斯基山脉玩。莫伊拉同学突然想划船到对岸找被削的Mercy玩，这里的每一艘船都是同一型号，能承受的重量都是一样的，并且每艘船都可以坐一个或者两个人。WC他们共有n个人，现在我们知道他们每个人的质量，而且每个人体重也不超过船的承重。可惜经费有限，他们必须租尽可能少的船，请问他们最少要租几艘船？ 
Input

第一行包含两个正整数n 和m ，n<=10^4,m<=2*10^9，表示人的数量和船的最大承重。 接下来n行，每行一个正整数，表示每个人的体重。体重不超过m。 

Output

一行一个整数表示最少需要的独木舟数。

Sample Input

3 6
1
2
3

Sample Output

2

 

解法： 先排序，最左边和最右边能放在一起就一起走，否则最右边自己走

#include <cstdio> 
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	vector<int> ve;
	int n, m;
	int heavy;
	int i, j, total;
	
	scanf("%d%d", &n, &m );
	while( n-- ){
		scanf("%d", &heavy );
		ve.push_back( heavy ); 
	}
	sort( ve.begin(), ve.end() );	/*排序*/ 
	total = 0;	/*记录独木舟的数量*/ 
	for( i=0, j = ve.size()-1; i<=j; j-- ){	/*每次最右的必定走*/ 
		if( ve[j] + ve[i] <= m ){	/*最右最左可以一起走*/ 
			total ++;
			i++;
		}
		else			/*最右自己走*/ 
			total++;
	}
	printf("%d\n", total );
	
	return 0;
}