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

解题思路:
贪心思想，尽量让价格最高的和价格最低的匹配；否则她单独一组
注意事项:
不要自己写排序，不然会时间超限，用qsort()快排函数解决
参考代码:

#include<stdio.h>

#include<stdlib.h>

int cmp(const void * a,const void * b) ;

int main()

{

int w,i=0,j,max,sum=0;

int n;

int price[30001];

scanf("%d",&w);

scanf("%d",&n);

while(n--)

{

scanf("%d",&price[i]);

i++;

} 

n=i;

qsort(price,n,sizeof(int),cmp);//快排函数qsort(),在stdlib.h库中；传入四个参数，1：要被排序的数组；2.要被排序的元素个数；3.每个数组元素的大小，用sizeof(）获得；4.自己写的cmp函数，用来定义是升序还是降序排序 

for(i=0,j=n-1;i<n;i++)//贪心思想，从价格最高的算起，如果它和价格最低的匹配，超过规定上限，就让它单独一组；否则就和价格最低的配对；i,j分别指向当前价格最高的和最低的，从两头向中间移 

{

if(i>j)

break;

if(price[i]+price[j]<=w)

j--;

sum++;

  } 

printf("%d",sum);

return 0;

}

int cmp(const void * a,const void * b)  

    {  

        return (*(int*)b-*(int*)a);//b>a 返回正值 ,这样使得快排函数按降序排序 ；若a在前b在后，则定义为升序排序 

    }