#P17971. Heuristic Knapsack

Heuristic Knapsack

Heuristic Knapsack

题目描述

有 nn 件物品,编号为 1,2,…,n1,2,\ldots,n,第 ii 件物品的重量为 wiw_i,价值为 rir_i。背包容量为 WW。

Alice 和 Bob 使用不同的贪心策略挑选物品:

  • Alice:重量优先。 将物品按重量从小到大排序,重量相同时按原编号从小到大排序。然后依次选取物品,直到遇到第一件放不进背包的物品时停止。她选取的是排序后序列的一个前缀。
  • Bob:价值优先。 将物品按价值从大到小排序,价值相同时按原编号从小到大排序。然后依次检查每件物品:若能够放进背包就选取,否则跳过这件物品并继续检查后面的物品。

某些重量或价值丢失了。每件物品的重量与价值中,至多一个未知,输入中用 00 表示未知值。

请把每个未知值补成 [1,109][1,10^9] 内的整数,使 Alice 与 Bob 最终选取的物品集合完全相同。集合中物品的选取顺序不需要相同。如果无法做到,报告无解。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例包含三行:

第一行两个整数 n,Wn,W。

第二行 nn 个整数 w1,w2,…,wnw_1,w_2,\ldots,w_n。

第三行 nn 个整数 r1,r2,…,rnr_1,r_2,\ldots,r_n。

输出格式

对于每个测试用例,如果无解,输出一行 No。

否则,输出一行 Yes,下一行输出补全后的 w1,…,wnw_1,\ldots,w_n,再下一行输出补全后的 r1,…,rnr_1,\ldots,r_n。所有原本已知的数值必须保持不变。

Yes 和 No 不区分大小写。如果有多种合法方案,输出任意一种。

数据范围

  • 1≤T≤1001\le T\le100;
  • 1≤n≤30001\le n\le3000,1≤W≤1091\le W\le10^9;
  • 0≤wi,ri≤1090\le w_i,r_i\le10^9,每个 ii 至少有一个值非零;
  • 所有测试用例的 nn 之和不超过 30003000;
  • 补全后的每个重量与价值均须在 [1,109][1,10^9] 内。

样例

输入

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 都先选第 22 件物品,再选第 11 件。第二组中,两人都选取第 11、33 件物品。最后一组无解。

来源与许可

原题:The 2025 Asia Chengdu Regional Contest,收录于 The 4th Universal Cup, Stage 4。本中文题面根据官方英文题面翻译整理,保留原题英文名称。原题及本译文采用 CC BY-SA 4.0 许可。