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

左手的ㄟ右手 2022-11-05 13:58 170阅读 0赞

**上一篇博客：[朴素Dijkstra算法][Dijkstra]**

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

原题链接：[纪念品分组][Link 1]

### 文章目录 ###

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

# 题目信息 #

## 题目描述 ##

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

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

## 输入描述 ##

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

--------------------

> 未完待续，持续更新中……  
> ![20210306223515499.png][]

[Dijkstra]: https://ac-fun.blog.csdn.net/article/details/114372108
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[Link 1]: https://www.lanqiao.cn/problems/532/learning/
[20210306223515499.png]: /images/20221023/3db586b0b44f44bc9e2ac7ef2658d773.png