纪念品分组 （C语言代码）快速排序

解题思路:进行快速排序后，再进行判断

参考代码:

#include <stdio.h>
#include <stdlib.h>
void quicksort(int [],int,int);
int partition(int [],int,int);

int main()
{
    int w,n,i,j,cnt=0;
    scanf("%d\n%d",&w,&n);getchar();
    //以下初始化、输入
    int* a=(int*)malloc(sizeof(int)*n);
    for(i=0;i<n;i++) scanf("%d",a+i);
  
    //以下代码快速排序
    quicksort(a,0,n-1);
    
    //以下代码统计可分组数
    i=0;j=n-1;
    while(i<j)
    {
        if(a[i]+a[j]<=w)
        {
            cnt++;i++;j--;
        }
        else {j--;cnt++;}
    }
    if(i==j)cnt++;
    
    //输出
    printf("%d",cnt);
    free(a);
}

int partition(int a[],int left,int right)
{
    int i,j,key;
    i=left;
    j=right;
    key=a[right];
    while(i<j)
    {
        while(i<j&&a[i]<=key)i++;
        if(i<j) a[j]=a[i];
        while(i<j&&a[j]>key)j--;
        if(i<j) a[i]=a[j];
    }
    a[j]=key;
    return j;
}

void quicksort(int a[],int left,int right)
{
    int intv;
    if(left<right)
    {
        intv=partition(a,left,right);
        quicksort(a,left,intv-1);
        quicksort(a,intv+1,right);
    }
}