#C12. [AHOI2021初中组]t2 坑(hole)
[AHOI2021初中组]t2 坑(hole)
题目描述
【题目背景】 买东西的路上小雪吸了好几口雾霾,最后打了个喷嚏。恶劣的天气、压抑的氛围让小雪心情越来越差,之后倒起了苦水:
“唉!今天又被一个不靠谱的同学坑了,浪费了我好多时间。”
“期中考试还早,有什么好焦虑的呢?别卷了,正好来看看最近在蛐蛐国流行的一个游戏吧。”
小雪看了游戏来了精神:看起来好像很解压。
【问题描述】
游戏在一个左右无限延伸的数轴上进行,上面有 n 只跳蚤和 m 个坑,它们都可以被抽象成数轴上的一个点。
玩家每回合需要选择让所有跳蚤一起向左/向右跳一个单位长度。如果一个代表跳蚤的点与一个代表坑的点重合了,跳蚤就会掉进坑中,发出惨叫后死去。
郁闷的小雪想用最快的时间杀死所有跳蚤,请你帮小雪计算一下这个最少的回合数。
输入格式
第一行两个空格隔开的正整数 n, m。
第二行 n 个空格隔开的整数 x1, x2, . . . , xn,其中 xi 表示第 i 只跳蚤初始时的坐标。
第三行 m 个空格隔开的整数 y1, y2, . . . , ym,其中 yi 表示第 i 个坑的坐标。
输入数据保证以上 n + m 个坐标两两互不相等。
输出格式
仅一行一个整数,表示杀死所有跳蚤的最少回合数。
3 2
3 -1 2
0 10
5
【样例 1 解释】 第一回合让所有跳蚤向右跳一步,第 2 个跳蚤进第一个坑,剩下两个跳蚤分别位于 4, 3。下面四回合让所有跳蚤向左跳,两个跳蚤都进入第一个坑,游戏结束。
数据范围
提示:本题输入规模较大,请避免使用过慢的输入方式。
• 对于 20% 的数据,保证 1 ≤ n ≤ 20, 1 ≤ m ≤ 300;
• 对于另外 20% 的数据,保证 1 ≤ n, m ≤ 300;
• 对于另外 20% 的数据,保证 1 ≤ xi, yi ≤ 2000;
• 对于另外 10% 的数据,保证 1 ≤ n, m ≤ 2000;
• 对于另外 10% 的数据,保证 m = 2;
• 对于 100% 的数据,保证 1 ≤ n, m ≤ 2 × 10^5, −10^9 ≤ xi, yi ≤ 10^9。