TDOG模拟 #8 多重影分身之术
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
“未-巳-寅——多重影分身之术!”
说完,Kiana一分为\(n\),\(n\)个影分身全部跳到了一根数轴上,其中第\(i\)个影分身的坐标为\(x_i\)。除了Kiana的影分身外,数轴上还有\(m\)个卷轴,其中第\(j\)个卷轴的坐标为\(y_j\)。Kiana的任务就是利用自己的影分身,拾取数轴上的全部卷轴。
具体来说,每秒钟Kiana的每个影分身都可以z各自选择向左或向右移动\(1\)个单位的距离,当然它们也可以选择原地不动。如果某个时刻,某个影分身的坐标和卷轴的坐标重叠,该卷轴会瞬间被拾取。
Kiana当然想知道,最少需要多少秒她的影分身们才能够拾取完所有的卷轴。由于Kiana自己不会算,所以希望你能够帮助她。
输入输出格式
输入格式
第一行包含两个正整数\(n\)和\(m\),分别表示Kiana的影分身数量和数轴上的卷轴数量。
第二行包含\(n\)个正整数,其中第\(i\)个正整数\(x_i\)表示第\(i\)个影分身的坐标。
第三行包含\(m\)个正整数,其中第\(j\)个正整数\(y_j\)表示第\(j\)个卷轴的坐标。
输出格式
输出共一行,包含一个正整数,表示拾取所有的卷轴所需的最少时间。
输入输出样例
输入样例#1:
2 4
3 7
5 11 1 9
输出样例#1:
6
输入样例#2:
输出样例#2:
样例解释
在输入输出样例1中,Kiana共有\(2\)个影分身,其坐标分别为\(3,7\),数轴上有\(4\)个卷轴,其坐标分别为\(5,11,1,9\)。
Kiana的影分身们可以按照如下方式移动:
坐标为\(3\)的影分身先向左走去拾取坐标为\(1\)的卷轴,消耗\(2\)秒钟时间,然后再转身去拾取坐标为\(5\)的卷轴,消耗\(4\)秒钟时间,总时间消耗为\(6\)秒钟
坐标为\(7\)的影分身先向左走去拾取坐标为\(9\)的卷轴,消耗\(2\)秒钟时间,再继续向左去拾取坐标为\(11\)的卷轴,消耗\(2\)秒钟时间,总时间消耗为\(4\)秒钟
综上所述,影分身们在\(6\)秒钟内能够拾取所有卷轴,可以证明这是用时最少的方案之一。
数据范围
对于\(20\%\)的数据,保证\(1\leq n,m\leq 50\)。
对于\(40\%\)的数据,保证\(1\leq n,m\leq 3000\)。
对于\(100\%\)的数据,保证\(1\leq n,m\leq 300000,1\leq x_i,y_j\leq 10^9\),所有的\(x_i,y_j\)互不相同。
上面每一档数据中,各有一组数据保证\(n=1\),还有一组数据保证\(n=2\)。
TDOG非专业级软件能力认证集训营CSP-S模拟 #2
- 状态
- 已结束
- 规则
- OI
- 题目
- 4
- 开始于
- 2023-10-12 08:30
- 结束于
- 2023-10-12 11:30
- 持续时间
- 3.0 小时
- 主持人
- 参赛人数
- 1