【练习】纪念品分组
纪念品分组
https://ac.nowcoder.com/acm/problem/16640
题目
题目描述： 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。
为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组。
但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。
为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
第 1 行包括一个整数 w，为每组纪念品价格之和的上限。
第 2 行为一个整数n，表示购来的纪念品的总件数。
第 3 ~ n+2 行每行包含一个正整数 pi ( 5 ≤ pi ≤ w ) ，表示所对应纪念品的价格。
包含一个整数，即最少的分组数目。
解析
根据题目意思，为什么要讲题目，没错我又看错题了。题目要求每组最多两个纪念品，要使组数尽量少（这么瞎，我选拔赛怎么办啊orz）。
- 既然要组数尽量少，非常容易的就会想到：每组的纪念品价格要尽量的大。
算法讲解：
- 我们要价格大，题目给了我们一个非常方便的条件：所有物品价格都没有要求价格大（虽然有也没事，这些买不了）。
- 那我们怎么分组呢？这道题毫无疑问就是贪心，而且贪的就是每个价格最大。
- 所以我们理所当然的就想到了：组里面放一个最大的，然后与之相配，就看能不能加一个最小的就可以了
（为什么一定是最小的呢？因为你最大的不用，给别的用也一样，别的要是只能用最小的，给他也没有意义，不如不给）。 - 所以我们取左右端点，判断当前最大最小是不是可以组队，不能组就缩右边，能就两边一起缩。
打代码哈：
- 我们先保存价值的数组。
- 然后排个升序。
- 然后左右区间进行操作就行了。
- 看代码哈~
AC代码
#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int INF = 0x3f3f3f3f;
const int MAX = 3e4 + 7;
int w, n, val[MAX];
//全局变量区
int main() {
IOS;
cin >> w >> n;
for (int i = 1; i <= n; i++) cin >> val[i];
sort(val + 1, val + 1 + n);
int l = 1, r = n, cnt = 0;
while (l < r) {
if (val[l] + val[r] <= w) l++;//这一对可以用，小的就也用上了
r--;
cnt++;
}
if (l == r) cnt++;
cout << cnt << endl;
return 0;
}
//函数区牛客算法竞赛入门课题解 文章被收录于专栏
憨憨的专栏
恒生电子公司氛围 51人发布