回忆是捉不到的月光 握紧就变黑暗 让虚假的背影 消失于晴朗----陈奕迅

系列文章目录

第一篇 【贪心算法】初步介绍

第二篇  【贪心算法】删数问题

第三篇  【贪心算法】排队打水

第四篇  【贪心算法】最大整数

第五篇  【贪心算法】纪念品分组

一、题目

1、原题

1143. 【贪心算法】纪念品分组 (Standard IO)

时间限制: 1000 ms  空间限制: 262144 KB  具体限制  

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

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

输入

输入包含n+2行：

第1行包括一个整数w，为每组纪念品价格之和的上限。

第2行为一个整数n，表示购来的纪念品的总件数。

第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。

输出

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

样例输入

100

9

90

20

20

30

50

60

70

80

90

样例输出

6

2、题意

输入一个有N个数字的数组，你要将它们分组（每组只能由两数组成），使各组两数之和（两数之和<=W）接近。输出满足上述条件的最小组数。

二、思路

1.读入数据

没什么难度，代码如下：

cin >>w>>n;
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }

2.核心内容

因为大小要最接近，因此用sort函数排序一下，然后左边（j),右边（i）所代表的物品相加后假若小于w就，可以将sum(表示最小组合数）++，还有记得把左端点j加1。

详细代码：

sort(p,p+n);
    int  j=0;
    int sum=0;
    for(int i = n-1; i>=j;i--)
  {
        if(p[i] + p[j] <= w)
    {
            sum++;
            j++;
        }
        else
    {
            sum++;
        }
    }

3.输出

输出同样很简单，用“cout"展现出sum就行了。

代码……就不单独展示了！

三、AC代码

#include<iostream>
#include<algorithm>
using namespace std;
int p[100005];
int w, n;
int main (){
    cin >>w>>n;
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    sort(p, p + n);
    int  j = 0;
    int sum =0;
    for(int i = n - 1; i >= j; i--){
        if(p[i] + p[j] <= w){
            sum++;
            j++;
        }
        else{
            sum++;
        }
    }
    cout << sum;
    return 0;
}

总结

这就是此题详解，欢迎关注！