[R15E]扫地机器人
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
时空限制
2S/512M
题目描述
数轴上有 个扫地机器人和 个垃圾, 号机器人的初始坐标为 ,第 个垃圾的坐标为 。
扫地机器人每秒的移动距离为 ,分为三个种类:
- 类机器人只能向左移动,也就是说如果现在有一个 类机器人位于坐标 ,那么 秒后它位于坐标 ;
- 类机器人只能向右移动,也就是说如果现在有一个 类机器人位于坐标 ,那么 秒后它位于坐标 ;
- 类机器人可以自己选择向左或向右移动,随时可以改变方向且改变方向不花时间,也就是说如果现在有一个 类机器人位于坐标 ,那么 秒后它可能位于坐标 或坐标 。
一个垃圾被任意一个扫地机器人经过时会被清理,清理垃圾不花时间。多个扫地机器人可以同时位于一个坐标。
求清理所有垃圾最少需要花多少秒。数据保证至少有一个 类机器人。
格式
输入格式
第一行包含两个整数 ,分别表示扫地机器人的数量和垃圾的数量。
第二行包含 个整数 ,分别表示每个扫地机器人的初始坐标。
第三行包含 个整数 ,分别表示每个扫地机器人的类型。
第四行包含 个整数 ,分别表示每个垃圾的坐标。
输出格式
输出一个整数表示清理所有垃圾最少需要花多少秒。
样例
样例输入 #1
3 6
3 9 14
3 2 3
6 15 1 9 8 4
样例输出 #1
7
样例解释 #1
其中一种方案为:
- 号机器人 秒向左移动到达坐标 , 秒向右移动到达坐标 ,过程中可以清理到垃圾:;
- 号机器人 秒向右移动到达坐标 ,过程中可以清理到垃圾:;
- 号机器人 秒向左移动到达坐标 ,过程中可以清理到垃圾:。
所有的垃圾都在 秒内被清理了。
样例输入 #2
1 2
500000000
3
1000000000 1
样例输出 #2
1499999998
数据规模
对于 的数据,,,,且对于 有 。
对于 的数据,,且对于 有 。
另有 的数据,。
对于 的数据,,,,。数据保证至少有一个 满足 。
代码源挑战赛 Round 15
- Status
- Done
- Rule
- DMY
- Problem
- 6
- Start at
- 2025-6-6 20:00
- End at
- 2025-6-6 21:30
- Duration
- 1.5 hour(s)
- Host
- Partic.
- 579