第六章42

标签：纪念品 int 每组 42 整数 最少 分组 第六章

【题目描述】

 

        ACM俱乐部成功举办了月赛，yyfish找来了cherry、CatCage、Ants等众位大牛帮忙负责月赛的纪念品发放工作。为使得参加月赛的同学所获得的纪念品价值相对均衡，他们要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，yyfish希望分组的数目最少。

 

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

 

【输入】

 

        有n+2行。第1行包含一个整数w（80 ≤ w ≤ 200），为每组纪念品价格之和的上限。第2行是一个整数n（1≤ n ≤ 30000），表示购来的纪念品的总件数。第3~n+2行每行包含一个正整数pi（5 ≤ pi ≤ w），表示所对应纪念品的价格。

 

【输出】

 

       仅一行。包含一个整数，即最少的分组数目。

 

【样例输入】

 

100

9

90

20

20

30

50

60

70

80

90

 

【样例输出】

 

6

#include<stdio.h>
int main()
{
    int max,n,i,j,t;
    scanf("%d\n%d",&max,&n);
    int sum=n;
    int m[n];
    for(i=0;i<n;i++)
    scanf("%d",&m[i]);
    for(i=0;i<n;i++)
    for(j=i;j<n;j++)
    if(m[i]<m[j])
    {
        t=m[i];
        m[i]=m[j];
        m[j]=t;
    }
    for(i=0;i<n;i++)
    for(j=i+1;j<n;j++)
    if(m[i]+m[j]<=max)
    {
        sum--;
        m[j]=max;
        break;
    }
    printf("%d",sum);
    return 0;
}

 

标签：纪念品,int,每组,42,整数,最少,分组,第六章
From： https://www.cnblogs.com/xrj1229/p/16882334.html