纪念品分组 （C语言代码）

解题思路:
这一题关键在于两个纪念品价格的搭配，在组价格不超出规定价格的前提下，如何分组才能使组数尽量少、组内两个价格之和不大于规定价格？这需要按价格从小到大排序，首先取出价格最小的纪念品，拿它和价格最大的搭配；若价格超出，发现价格最大的纪念品：加当前价格最小的纪念品都超出，和其它纪念品搭配必然超出规定的组价格，所以只能单独分一组；这之后，小价格先不变，大价格应更便宜，才能与小价格搭配，若发现两个一组价格合适，分组成功后，这两个纪念品已进入分组，不再寻找搭配，下次进行分组的小价格更贵、大价格更便宜；以此类推，当小价格与大价格相同时，其它组已分好，当前纪念品成为最后一组，当大价格小于小价格时，没有更多分组。

注意事项:
b指向小价格，t指向大价格，只有在b<t时，才有必要改变b、t，使它们更靠近。

参考代码:

#include<stdio.h>
#include<stdlib.h>
int a[30001];
int main(){
    int y(const void *,const void *);
    int i,W,n,b,t,c;
    scanf("%d%d",&W,&n);
    for(i=0;i<n;i++) scanf("%d",a+i);   //输入n个纪念品的价格
    qsort(a,n,sizeof(int),y);           //按价格从小到大排序
    c=b=0;t=n-1;                        //b和t分别指向小价格和大价格
    while(b<=t){
        while(a[b]+a[t]>W&&b<t){        //若两个一组价格超出
            t--;                        //小价格不变，大价格应更便宜
            c++;                        //上次的大价格(加当前最小价格都不行)单独分一组
        }
        if(a[b]+a[t]<=W&&b<t){          //若两个一组价格合适
            b++;                        //往后小价格更贵
            t--;                        //往后大价格更便宜
            c++;                        //合适的两个一组
        }else if(b==t){                 //若小价格与大价格相同
            c++;                        //其它组已分好，最后单独一组
            break;
        }
    }
    printf("%d\n",c);
    return 0;
}
int y(const void *a,const void *b){
    return *(int *)a-*(int *)b;
}