1143 纪念品分组
题目描述 Description
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入描述 Input Description
包含n+2行：
第1行包括一个整数w，为每组纪念品价格之和的上限。
第2行为一个整数n，表示购来的纪念品的总件数。
第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。
输出描述 Output Description
仅一行，包含一个整数，即最少的分组数目。
样例输入 Sample Input
100
9
90
20
20
30
50
60
70
80
90
样例输出 Sample Output
6
数据范围及提示 Data Size & Hint
50%的数据满足：1 <= n <= 15
100%的数据满足：1 <= n <= 30000, 80 <= w <= 200
思路：将要分发的物品按照从大到小的顺序排序，之后第一个去和最后一个相加，如果小于规定数n，且没有被分过组，则分类总数sum加1，如果不行，那往前一个数一定比最后一个数大，就不用再判断了，也就是第一个数只能单独分一个组，继续第二个数和最后一个未分组的数比（分过组的标记好。），直到所有数都被分组即可
例如样例给的数据：90,90,80,70,60,50,30,20,20（排序后）,一知分组不能超过100
首先，90+20>100，不行，90单独分一组，sum=1；
第二，90同理单独一组，sum=2；
第三，80+20==100,那么80和20一组，sum=3；
第四，70+20<100,70和20一组，sum=4；
第五，60+30<100,60和30一组，sum=5；
第六，由于其他所有数都参与了分组，只剩下50自己，所以它自己一组，sum=6；
所以答案为6
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct node
{
int flag;
int num;
}a[30010];
int cmp(node x,node y)
{
if(x.num!=y.num) return x.num>y.num;
}
int main()
{
int i,j,n,m,sum,x;
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
for(i=0;i<m;i++)
scanf("%d",&a[i].num);
sort(a,a+m,cmp);
sum=0;
for(i=0;i<m;i++)
{
x=0;
for(j=m-1;j>=0;j--)
{
if(j==i)
continue;
if(a[i].num+a[j].num<=n&&a[j].flag==0&&a[i].flag==0)
{
a[j].flag=1;
a[i].flag=1;
sum++;
x=1;
break;
}
}
if(x==0&&a[i].flag==0){ sum++;}
}
printf("%d\n",sum);
return 0;
}
