纪念品分组——复习qsort排序

解题思路:

注意事项:如果要输出纪念品的组合，还要考虑纪念品组合的价值相对均衡

参考代码:

#include<stdio.h>
#include <malloc.h>
#include <stdlib.h> 
#include <string.h>
int compare(const void* p1, const void* p2)
{
    return (*(int*)p1 - *(int*)p2);
}
int main()
{
    int w=0, n=0;
    scanf("%d%d", &w, &n);
    int count = 0;//分组数
    int* pi = NULL;
    pi=(int*)malloc(n * sizeof(int));
    if (pi == NULL)
    {
        return 1;
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &pi[i]);
    }
    //递增排序
    qsort(pi, n, sizeof(int), compare);
    //最小价值与最大价值相加
    int left = 0, right = n - 1;
    while (left < right)
    {
        //相加超过w，则最大价值的纪念品单独一组
        if (pi[left] + pi[right] > w)
        {
            right--;//转到未分组的最大的价值
            count++;//组数加一
        }
        //相加不超过w，则两纪念品分为一组
        else
        {
            left++;//转到未分组的最小价值
            right--;
            count++;
        }
    }
    //相等，还剩一个纪念品，单独一组
    if (left == right)
    {
        count++;
   }
    printf("%d", count);
    free(pi);
    pi = NULL;
    return 0;
}