纪念品分组
发布日期:2022-02-08 04:20:45
浏览次数:4
分类:技术文章
本文共 788 字,大约阅读时间需要 2 分钟。
元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品, 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。
你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
输入格式
输入包含 n+2n+2 行。
第 11 行包括一个整数 w(80 \leq w \leq 200)w(80≤w≤200),为每组纪念品价格之和的上限。
第 22 行为一个整数 n(1\leq n \leq 3\times 10^4)n(1≤n≤3×104),表示购来的纪念品的总件数。
第 33 至第 n+2n+2 行每行包含一个正整数 P_i (5 \leq P_i \leq w)Pi(5≤Pi≤w)表示所对应纪念品的价格
#include<bits/stdc++.h>
using namespace std; #define N 30002 int main () { int n,s,c; int w,a[N],j=1,bo[N]={0},sum=0; cin>>w; cin>>n; memset(bo,0,sizeof(bo)); for(int i=0;i<n;i++){ cin>>a[i]; } sort(a,a+n); for(s=0;s<n;s++){ for(c=n-1;c>=0;c--){ if(a[s]+a[c]<=w&&!bo[s]&&!bo[c]){ bo[s]=1; bo[c]=1; sum++; } } } for(int i=0;i<n;i++){ if(bo[i]==0){ sum++; } } cout<<sum<<endl; return 0; }转载地址:https://blog.csdn.net/weixin_38960774/article/details/79370133 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年04月16日 21时16分40秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
C++ 多字节与宽字符串的相互转换
2019-04-26
OpenMP并行加速笛卡尔乘积
2019-04-26
C++ 为什么要引入异常处理机制
2019-04-26
C++ 抛出异常与传递参数的区别
2019-04-26
Golang map 第一式:快速上手
2019-04-26
Golang 函数返回类型是接口时返回对象的指针还是值
2019-04-26
Golang 方法接收者为值与指针的区别
2019-04-26
认识目标文件的格式—— a.out COFF PE ELF
2019-04-26
Golang 函数耗时统计
2019-04-26
Linux 命令(69)—— objcopy 命令
2019-04-26
Linux 命令(70)—— size 命令
2019-04-26
认识目标文件的结构
2019-04-26
经典算法——单向链表反转
2021-06-29
认识目标文件的符号
2021-06-29
C 移位运算
2021-06-29
Golang 主机字节序的判断
2021-06-29
Golang bytes.Buffer 用法精述
2021-06-29
Golang sync.Map 简介与用法
2021-06-29
Golang sync.WaitGroup 简介与用法
2021-06-29
Golang sync.Pool 简介与用法
2021-06-29