【贪心算法】纪念品分组

贪心算法】纪念品分组"/>

【贪心算法】纪念品分组

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

系列文章目录

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

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

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

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

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

一、题目

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;
} 

总结

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