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

解题思路:

用qsort函数对每件纪念品的价格进行降序排序，然后将第一个（即最大）与最后一个（即最小）一起和规定钱数比较。以测试样例为例，排序后为 90 90 80 70 60 50 30 20 20 显然第一个与最后一个无法分在一组，只能90独自为一组，然后在将第二个与从下方往上数的第一个一起与100比较，依次类推。

注意事项:

时间问题

参考代码:

#include <stdio.h>

#include <stdlib.h>

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

{

    return *(int *)b - *(int *)a;

}

int main()

{

    int va[30005] = {0};

    int i , n , money , group=0 , a=1 , b=0;

    scanf("%d",&money);

    scanf("%d",&n);

    for(i=0; i<n; i++)

    {

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

    }

    qsort(va,n,sizeof(va[0]),cmp);

    a = 0;

    b = n-1;

    while(a != b&& a-1 != b)

    {

        if(va[a] + va[b] <= money)

        {

            group+=1;

            va[a] = 0;

            a+=1;

            va[b] = 0;

            b-=1;

        }

        else

        {

            group+=1;

            va[a] = 0;

            a+=1;

        }

    }

    for(i=a; i<=b; i++)

    {

        if(va[i]!=0)

            group+=1;

    }

    printf("%d",group);

    return 0;

}