记录编号	130182	评测结果	AAAAAAAAAAT
题目名称	[NOIP 2007]纪念品分组	最终得分	90
用户昵称	fyb	是否通过	未通过
代码语言	C++	运行时间	2.415 s
提交时间	2014-10-21 20:51:29	内存使用	0.37 MiB

#include <stdio.h>
#include <stdlib.h>

#define NMAX 30000

int p[NMAX];

int comp(const void *a,const void *b){
	return *(int*)a-*(int*)b;
}

int main(){
	int w,n;
	int num;
	int i,j;

	freopen("group.in","r",stdin);
	freopen("group.out","w",stdout);

	scanf("%d",&w);
	getchar();
	scanf("%d",&n);
	getchar();

	for(i=0;i<n;i++){
		scanf("%d",p+i);
		getchar();
	}

	num=n;

	qsort(p,n,sizeof(int),comp);

	for(i=n;i;i--){
		if(p[i-1]==0)continue;
		for(j=i-1;j;j--){
			if(p[j-1]==0)continue;
			if(p[i-1]+p[j-1]<=w){
				p[i-1]=0;
				p[j-1]=0;
				num--;
				break;
			}
		}
	}

	printf("%d",num);
	return 0;
}