Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5633 --2、发送快递(express)
5633: 2、发送快递(express)
警告!
题目
状态
题解(1)
题目描述
小华有 n 本不同的书(编号为 1,2,3,.....,n),重量分别是 a1、 a2、……、an公斤(重量可以相同)。他想把这些书以快递的方式发给自己 的好朋友,要求每个包裹的重量不能超过 m 公斤(可以等于 m 公斤),并且 小华想把其中一些书(一组书,用书的编号给出来)放在一个包裹里,应该 如何打包才能使得快递件数最少。
输入
第一行,包含两个整数 n、m,之间用一个空格隔开,分别表示书的数量 和快递包裹的最大重量。 第二行 n 个整数 ai,表示 n 本书的重量,每两个整数之间用一个空格隔 开。 第三行一个整数 s,表示一共有 s 组书(每组书需要打包在一起)。如果 s=0,则无此限制。数据保证每组书的重量不超过 m。 第四行开始共 s 行,每行若干个整数,表示必须放在一个包裹里的书的 编号,每两个整数之间用一个空格隔开。
输出
一个整数,即快递最少件数。
样例输入输出
输入#1
复制
5 10 8 4 8 2 5 0
输出#1
复制
3
输入#2
复制
10 80 49 11 44 18 28 24 19 10 27 29 2 1 5 4 8 2
输出#2
复制
4
提示
【样例 1 说明】 第 1 本和第 4 本打包,重量是 10 公斤。 第 2 本和第 5 本打包,重量是 9 公斤。 第 3 本单独打包,重量是 8 公斤。 所以一共 3 件快递。 【样例 2 说明】 第 1 本和第 5 本打包,第 2 本、第 4 本、第 8 本和第 10 本打包, 第 3 本和第 7 本打包,第 6 本和第 9 本打包。所以一共 4 件快递。 【数据范围和限制】 对于 40%的数据,1 ≤ n ≤ 10^5,1 ≤ ai ≤ 100,s=0,m 的值保证有解。 对于 100%的数据,1 ≤ n ≤ 10^5,1 ≤ ai ≤ 100,0 ≤ s ≤ 100,m 的值保证有解。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及+/提高-
标签
贪心
点击显示
if ($pr_flag) { ?>
递交数
97
已通过
1
} ;?>
通过率
2%
时间限制
1 秒
内存限制
128 MB
来源
2021CSP山东小学
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和