首页 > 试题广场 >

[NOIP2007]纪念品分组

[编程题][NOIP2007]纪念品分组
  • 热度指数：307 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入描述:
第 1 行包括一个整数 w，为每组纪念品价格之和的上限。
第 2 行为一个整数n，表示购来的纪念品的总件数。
第 3 ~ n+2 行每行包含一个正整数 pi ( 5 ≤ pi ≤ w ) ，表示所对应纪念品的价格。


输出描述:
包含一个整数，即最少的分组数目。
示例1

输入

100
9
90
20
20
30
50
60
70
80
90

输出

6

备注:
50%的数据满足：1 ≤ n ≤ 15
100%的数据满足：1 ≤ n ≤ 30000, 80 ≤ w ≤ 200
算法知识视频讲解
开通博客
头像 savage
发表于 2019-08-22 16:26:28
题目描述 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的 展开全文
去ta的博客 赞 (12) 回复(1) 收起
头像 平凡的小白
发表于 2020-05-29 14:04:34
思路：每一组最多两个礼品，贪心。1.如果枚举最小的礼品，要去找是否有礼品和它组队，而且枚举下一个礼品时还要判断是否组队了，比较麻烦。2.如果枚举最大的礼品，升序排序，如果最前面的礼品可以和这个礼品放一组，那么去掉这两个礼品，继续枚举下一个礼品。3.比较简单，代码会好懂些。Code： #include 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 MasterSPP
发表于 2020-07-08 20:07:41
题解：我的代码很简单，步骤一：先用sort把纪念品的价格排序。步骤二：然后从价格序列的两头同时开始，如果最高价格a[n-1]加上最低价格a[0]超过了给定的价格上限，那就试试a[n-2]和a[0]相加，从右到左直至有一个高价格的能和价格最低的分到一起。 价格太高不能和别的纪念品一起分组没关系，换它左 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 hh想实习
发表于 2020-05-19 17:25:50
先排序，用双指针扫描定义 L 为左指针，R 为右指针，总组数sum=0，每次相加左右指针指向的元素，若大于价格上限则R--，sum++;否则两指针同时往中间移一位即L++，R--；如果L==R，说明只剩下一个数了，总组数sum++，如果L>R，就结束了。代码： #include<bits 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 虽然吧_但是
发表于 2020-05-21 19:52:30
很明显就是一道关于背包的贪心问题那么根据贪心策略 固定容量的背包，装多样物品，使得背包数最小首先把大的装入背包，如果能匹配到一个最小的，他们的和小于容量就是优解 因为之前的最小的，会为后面稍大的提供空间，否则剩余的会超出容量达不到最优（我记得紫书上有讲） #include <bits/stdc 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ziuch
发表于 2020-08-21 16:31:14
题目描述 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 月下八哥
发表于 2021-01-18 13:45:23
一道贪心题上代码： #include<iostream> #include<algorithm> using namespace std; int a[100050]; int main() { int w, n; int ans = 0; cin 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 河婆虚
发表于 2022-05-24 17:19:42
#include<bits/stdc++.h> #define io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long int ll; typedef pai 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 青笙
发表于 2021-12-16 20:39:47
阅读完此题，你会发现，解决此题的关键是如何让两个数“尽可能”相加成一个值，这个值要小于等于w(w为每组纪念品价格之和的上限)，所以，我们要做的是便是如何“凑出”这个数，我们可以先把这些数放入一个数组中，然后通过数组中的sort()方法对数组进行排序，使其从小到大的排列，接下来我们要做的是“凑数”，我 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-05-21 20:18:53
解题思路 贪心，每组最多2个纪念品，那么对于大的，如果还剩下的最小的都不能和你组队，其他人也不难了，只能自己开个盒子。 那么直接升序排序只后，双指针遍历一遍即可。 #include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

NOIP复赛 排序 贪心
难度：
1条回答 3845浏览

热门推荐

通过挑战的用户

相关试题

[NOIP2007]纪念品分组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号