蓝桥杯纪念品分组（贪心，排序）

上一篇博客：朴素Dijkstra算法

写在前面：大家好！我是AC-fun,我的昵称来自两个单词Accepted和fun。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：https://ac-fun.blog.csdn.net/。非常感谢大家的支持。一起加油，冲鸭！
用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง

原题链接：纪念品分组

文章目录

题目信息
- 题目描述
- 输入描述
- 输出描述
- 输入样例
- 输出样例
题解
- 解题思路
- 解题代码

题目信息

题目描述

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

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

输入描述

第 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

题解

解题思路

本题是一个贪心问题，分组要求是每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数 w。可以先将所有输入的纪念品的价格从小到大排序，然后使用 双指针算法 每次从后取一个还未取到的价格最大的纪念品，从前取一个还未取到的价格最小的纪念品，判断这两个纪念品的价格之和是否大于 w，如果大于 w，说明此时价格最大的纪念品只能自己一组，然后使指向价格最大的纪念品的指针向前移动一位。否则说明这两个纪念品可以成为一组，此时让指向价格最小的纪念品的指针同时也向后移动一位。然后继续判断下一组纪念品。

每次确定好一组纪念品之后都使记录最少分组数目的计数器加一。直到这两个指针相遇，结束遍历。最后输出结果即可。

解题代码

#include <iostream>
#include<algorithm>
using namespace std;
const int N = 30010;
int w, n;
int ans;
int q[N];
int main()
{ 
    cin >> w >> n;
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    sort(q, q + n);
    int j = 0;
    for (int i = n - 1; i >= j; i--) { 
        if (q[i] + q[j] <= w) { 
            ans++;
            j++;
        } else ans++;
    }
    cout << ans;
    return 0;
}