纪念品分组-题解（C语言代码）（笑笑）

解题思路:

注意事项:

参考代码:

/*******************解题思路***********************

将所有礼品价值进行排序————>判断排序后首尾两数之和与最大价值谁大（因为每组不超过2个物品）

                                                 ————>在分类(谁大），然后讨论

(仅提供思路，具体实现方法看代码)

*/

#include<stdio.h>

void sort(int n,int max);//排序

int cheak(int *,int,int); //找出最小组

/******************************************/

int main ()

{

    int max;     //每组能拥有的最大价值

    int n;       //礼品数

    int min;     //最小组数

scanf("%d",&max);

scanf("%d",&n);

sort(n,max);  //排序

return 0;

}

/******************************************/

void sort(int n,int max)

{

int num[n];  //储存排序后的数组

int a;       //中间量

int min;

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

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

for(int i=0;i<n;i++)    //冒泡排序

  for (int j=i;j<n;j++){

  if(num[i]<num[j])

  {

  a=num[i];

  num[i]=num[j];

  num[j]=a;

  }

  }

min=cheak(num,max,n);

printf ("%d\n",min);

}

/******************************************/

int cheak(int *num,int max,int n) //找出最小组

{      

int min=0;          //最小组数

int n1=n-1;

for(int i=0;i<n;)    //思路找排序后，首尾两端的和与每组最大值比较

{

if(i!=n1&&num[i]+num[n1]<=max)

{

min++;

i++;

n1--;

}

else

{

i++;

min++;}

if(i>n1)

break;

  }

return min;

}