题目描述
原题来自：USACO
已知原数列
a_1,a_2,\cdots,a_n
a1
,a2
,⋯,an
中的前
1
1 项，前
2
2 项，前
3
3 项，
\cdots
⋯ ，前
n
n 项的和，以及后
1
1 项，后
2
2 项，后
3
3 项，
\cdots
⋯ ，后
n
n 项的和，但是所有的数都被打乱了顺序。此外，我们还知道数列中的数存在于集合
S
S 中。试求原数列。当存在多组可能的数列时，求字典序最小的数列。
输入
第
1
1 行，一个整数
n
n 。
第
2
2 行，
2 \times n
2×n 个整数，注意：数据已被打乱。
第
3
3 行，一个整数
m
m ，表示
S
S 集合的大小。
第
4
4 行，
m
m 个整数，表示
S
S 集合中的元素。
输出
输出满足条件的最小数列。
样例输入
5
1 2 5 7 7 9 12 13 14 14
4
1 2 4 5
样例输出
1 1 5 2 5
提示
数据范围与提示
样例解释
从左往右求和 从右往左求和
\phantom{0}1=1\phantom{+1+5+2+5}
01=1+1+5+2+5
\phantom{0}5=\phantom{1+1+5+2+}5
05=1+1+5+2+5
\phantom{0}2=1+1\phantom{+5+2+5}
02=1+1+5+2+5
\phantom{0}7=\phantom{1+1+5+}2+5
07=1+1+5+2+5
\phantom{0}7=1+1+5\phantom{+2+5}
07=1+1+5+2+5
12=\phantom{1+1+}5+2+5
12=1+1+5+2+5
\phantom{0}9=1+1+5+2\phantom{+5}
09=1+1+5+2+5
13=\phantom{1+}1+5+2+5
13=1+1+5+2+5
14=1+1+5+2+5
14=1+1+5+2+5
14=1+1+5+2+5
14=1+1+5+2+5
来源/分类
ybttg 搜索 剪枝优化