牛客HFL
2024-02-06 20:23 山东寿光胡营小学 算法工程师
关注
发送快递(express)
描述
小华有 n 本不同的书（编号为 1，2，3，.....，n），重量分别是 a1、a2、……、an公斤（重量可以相同）。他想把这些书以快递的方式发给自己的好朋友，要求每个包裹的重量不能超过 m 公斤（可以等于 m 公斤），并且小华想把其中一些书（一组书，用书的编号给出来）放在一个包裹里，应该如何打包才能使得快递件数最少。
输入
输入文件名为 express.in
第一行，包含两个整数 n、m，之间用一个空格隔开，分别表示书的数量和快递包裹的最大重量。
第二行 n 个整数 ai，表示 n 本书的重量，每两个整数之间用一个空格隔开。
第三行一个整数 s，表示一共有 s 组书（每组书需要打包在一起）。如果 s=0，则无此限制。数据保证每组书的重量不超过 m。
第四行开始共 s 行，每行若干个整数，表示必须放在一个包裹里的书的编号，每两个整数之间用一个空格隔开。
输出
输出文件名为 express.out
输出文件一行，一个整数，即快递最少件数。
输入样例 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 ≤ 105，1 ≤ ai≤ 100，s=0，m 的值保证有解。
对于 100%的数据，1 ≤ n ≤ 105，1 ≤ ai≤ 100，0 ≤ s ≤ 100，m的值保证有解。
查看原帖
1 评论
查看13道真题和解析
牛客热帖
更多
正在热议
更多
# 中美关税战对我们有哪些影响 #
17286次浏览 230人参与
# 秋招感动瞬间 #
16242次浏览 124人参与
# 实习进度记录 #
7282次浏览 50人参与
# 参加完秋招的机械人，还参加春招吗？ #
35460次浏览 395人参与
# 春招进度记录 #
5931次浏览 10人参与
# 校招求职有谈薪空间吗 #
122844次浏览 1695人参与
# 摸鱼打卡站 #
34669次浏览 657人参与
# 找工作如何保持松弛感？ #
29171次浏览 500人参与
# 怎么防止在试用期被辞退 #
112924次浏览 856人参与
# 阿里巴巴工作体验 #
14074次浏览 45人参与
# 工作经验重要还是工资重要？ #
35480次浏览 448人参与
# tplink提前批进度交流 #
152541次浏览 1313人参与
# 滴滴工作体验 #
19119次浏览 100人参与
# 央国企投递记录 #
76231次浏览 1294人参与
# 机械人，你被简历秒挂的企业有哪些？ #
33765次浏览 254人参与
# 如果没找到工作，考公是你的退路吗 #
21058次浏览 235人参与
# 每人推荐一个小而美的高薪公司 #
72055次浏览 1354人参与
# 机械人求职现状 #
13004次浏览 119人参与
# 硬件人的简历怎么写 #
250820次浏览 2870人参与
# 新凯来求职进展汇总 #
20603次浏览 72人参与