Skip to content

14064: 【原4064】射击

题目

题目描述

author: BowenTan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4064

Description

在一个周长为L圆形的星球上,等距离地有L个点,编号分别为1, 2, ..., L,相邻两个点之间距离都是1, 特别地,1号点和L号点之间的距离也是1。

现在两军交战,双方各有n名士兵,位置分散在这个星球上,而其中一方的领导,就是你。

你命令你的士兵朝对方的士兵开枪,每个人都要瞄准一名对方的士兵,并且对方的每名士兵都要被一名你的士兵瞄准。每名士兵可以向自己的左边或右边开枪,在这个方向上与目标的连线就是这一次射击的弹道。

一般来说,我们认为弹道的总长度越小,这次行动成功率越大。

请算出怎么样分配每个人的目标能够使得弹道总长度最小,当然,方案可能不唯一,你只需要输出最小的总长度。

input format

本题包含多组输入数据,数据开始首先输入数据组数T(T <= 3)

每组数据的第一行包含两个数n, L,意义如题目描述。

第二行有n个数,表示n个你的士兵所处的位置。

第三行有n个数,表示n个对方士兵所处的位置。

output format

对于每一组输入,都输出最小的总弹道长度。

sample input

2
3 15
1 2 10
11 12 13
4 12
2 5 8 11
6 9 12 3

sample output

9
4

explanation

第一组,方案为1->2, 2->3, 3->1

第二组,方案为1->4, 2->1, 3->2, 4->3

limits

  • 对于20%的数据,n<=1000
  • 对于100%的数据,n<=10^5, L<=10^9

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!