2782.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 //#define debug 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 3000000
#define NMAX 100000
int N;
int l;
int a[NMAX];
void input()
{
	int i;
	scanf("%d%d",&N,&l);
	for(i=0;i<N;i++)
	{
		scanf("%d",&a[i]);
	}
	
}
int cmp(const void *a,const void *b)
{
	return *(int*)b-*(int*)a;
}
int flag[NMAX]={0};
void solve()
{
	qsort(a,N,sizeof(int),cmp);	
	int p,q;
	p=0;
	q=N-1;

	int ans=0;
	int last;
	
	while(1)
	{

		if(flag[p])
			break;
		
		last=l;
		if(a[p]<=last)
		{
			last-=a[p];
			flag[p]=1;
			p++;
		}
		if(a[q]<=last)
		{
			last-=a[q];
			flag[q]=1;
			q--;
		}
		ans++;
	}
	printf("%d",ans);
}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);

#endif
	input();
	solve();
	
		
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}