#P17971. Heuristic Knapsack
Heuristic Knapsack
Heuristic Knapsack
题目描述
有 件物品,编号为 ,第 件物品的重量为 ,价值为 。背包容量为 。
Alice 和 Bob 使用不同的贪心策略挑选物品:
- Alice:重量优先。 将物品按重量从小到大排序,重量相同时按原编号从小到大排序。然后依次选取物品,直到遇到第一件放不进背包的物品时停止。她选取的是排序后序列的一个前缀。
- Bob:价值优先。 将物品按价值从大到小排序,价值相同时按原编号从小到大排序。然后依次检查每件物品:若能够放进背包就选取,否则跳过这件物品并继续检查后面的物品。
某些重量或价值丢失了。每件物品的重量与价值中,至多一个未知,输入中用 表示未知值。
请把每个未知值补成 内的整数,使 Alice 与 Bob 最终选取的物品集合完全相同。集合中物品的选取顺序不需要相同。如果无法做到,报告无解。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例包含三行:
第一行两个整数 。
第二行 个整数 。
第三行 个整数 。
输出格式
对于每个测试用例,如果无解,输出一行 No。
否则,输出一行 Yes,下一行输出补全后的 ,再下一行输出补全后的 。所有原本已知的数值必须保持不变。
Yes 和 No 不区分大小写。如果有多种合法方案,输出任意一种。
数据范围
- ;
- ,;
- ,每个 至少有一个值非零;
- 所有测试用例的 之和不超过 ;
- 补全后的每个重量与价值均须在 内。
样例
输入
6
3 5
0 2 3
2 4 0
3 5
2 3 0
4 0 2
3 1000000000
0 0 1000000000
2 3 1
5 1
0 1 1 1 0
3 8 0 7 9
5 1000000000
0 0 0 1 0
1 9 3 9 10
3 1000000000
500000001 500000000 0
1000000000 999999998 1
输出
Yes
3 2 3
2 4 1
Yes
2 3 2
4 1 2
Yes
1000000000 999999999 1000000000
2 3 1
Yes
1000000000 1 1 1 1000000000
3 8 1 7 9
Yes
1000000000 1000000000 1000000000 1 999999999
1 9 3 9 10
No
样例说明
第一组中,Alice 和 Bob 都先选第 件物品,再选第 件。第二组中,两人都选取第 、 件物品。最后一组无解。
来源与许可
原题:The 2025 Asia Chengdu Regional Contest,收录于 The 4th Universal Cup, Stage 4。本中文题面根据官方英文题面翻译整理,保留原题英文名称。原题及本译文采用 CC BY-SA 4.0 许可。