AT_past202303_m.お片付け
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有 N 个包裹,编号为 1 到 N。第 i 个包裹的体积为 Ai。
有 M 个箱子,编号为 1 到 M,按照编号从左到右依次排成一排:第 1 个箱子在最左边,第 M 个箱子在最右边。第 i 个箱子的体积为 Bi。
每个箱子可以装任意数量的包裹,只要包裹的总体积不超过该箱子的体积。
对于每个包裹,按照 1 到 N 的顺序,Takahashi 会尝试如下操作:
- 将该包裹放入第一个能够装下它的最左边的箱子。
请你判断 Takahashi 能否将所有包裹都放入箱子中。
如果可以,请输出所有包裹放入箱子后,每个箱子中包裹的总体积;如果不可以,请输出无法放入箱子的包裹中编号最小的一个。
输入格式
输入按如下格式从标准输入中给出:
N M
A1 A2 … AN
B1 B2 … BM
输出格式
如果 Takahashi 能将所有包裹都放入箱子中:
第一行输出 Yes。
第二行输出 C1,C2,…,CM,用空格隔开,其中 Ci 表示将所有包裹放入箱子后第 i 个箱子的包裹总体积。
如果 Takahashi 不能将所有包裹都放入箱子中:
第一行输出 No。
第二行输出无法放入箱子的包裹中编号最小的一个。
输入输出样例
输入#1
3 3 4 7 3 10 4 8
输出#1
Yes 7 0 7
输入#2
3 2 4 7 3 10 4
输出#2
No 2
输入#3
5 5 5 4 3 2 1 1 2 3 4 5
输出#3
Yes 1 2 3 4 5
说明/提示
样例解释 1
Takahashi 会按以下方式操作:
- 包裹 1 可以放入箱子 1、2、3,选择最左边的箱子 1 放入。
- 包裹 2 只能放入箱子 3,放入该箱子。
- 包裹 3 可以放入箱子 1 或箱子 2,选择最左边的箱子 1 放入。
注意,当尝试放包裹 2 时,包裹 1 已经在箱子 1 中,因此包裹 2 不能放进箱子 1。
所有包裹放入箱子后:
- 箱子 1 内有包裹 1 和 3,总容量为 3+4=7;
- 箱子 2 没有包裹,总容量为 0;
- 箱子 3 内有包裹 2,总容量为 7。
样例解释 2
Takahashi 会按以下方式操作:
- 包裹 1 可以放入箱子 1 或 2,选择最左边的箱子 1 放入。
- 包裹 2 无法放入任何一个箱子。
数据范围
- 1≤N≤2×105
- 1≤M≤2×105
- 1≤Ai,Bi≤109
- 输入中所有值均为整数。
由 ChatGPT 5 翻译
输入解题思路,AI测评打分。不知道怎么写?