贪心算法】纪念品分组"/>
【贪心算法】纪念品分组
回忆是捉不到的月光 握紧就变黑暗 让虚假的背影 消失于晴朗----陈奕迅
系列文章目录
第一篇 【贪心算法】初步介绍
第二篇 【贪心算法】删数问题
第三篇 【贪心算法】排队打水
第四篇 【贪心算法】最大整数
第五篇 【贪心算法】纪念品分组
一、题目
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;
}
总结
这就是此题详解,欢迎关注!
更多推荐
【贪心算法】纪念品分组
发布评论