题目详情题解（0）讨论（0）提交记录（0）

AT_abc273_f.[ABC273F] Hammer 2

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君现在在数轴的原点。他想移动到坐标 XX 处的终点。

在数轴上有 NN 面墙和 NN 把锤子。

  • 在坐标 Y1,Y2,…,YNY_1,Y_2,\dots,Y_N 处分别有类型为 1,2,…,N1,2,\dots,N 的墙。
    • 一开始，高桥君无法穿越任何墙。
  • 在坐标 Z1,Z2,…,ZNZ_1,Z_2,\dots,Z_N 处分别有类型为 1,2,…,N1,2,\dots,N 的锤子。
    • 当高桥君到达有锤子的坐标时，他会获得该处的锤子。
    • 类型 ii 的锤子只能用来破坏类型 ii 的墙。只有在获得类型 ii 的锤子后，才能破坏并通过类型 ii 的墙。

请判断高桥君是否能够到达终点。如果可以，请输出最小的移动距离。

输入格式

输入通过标准输入按以下格式给出。

NN XX Y1Y_1 Y2Y_2 …\dots YNY_N Z1Z_1 Z2Z_2 …\dots ZNZ_N

输出格式

如果高桥君可以到达终点，请输出最小的移动距离（整数）。
如果无法到达，请输出 −1-1。

输入输出样例

  • 输入#1

    3 10
-2 8 -5
5 -10 3

    输出#1

    40

  • 输入#2

    5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

    输出#2

    1

  • 输入#3

    1 100
30
60

    输出#3

    -1

  • 输入#4

    4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

    输出#4

    4078987507

说明/提示

限制条件

  • 所有输入均为整数。
  • 1≤N≤15001\leq N\leq 1500
  • 1≤∣X∣,∣Yi∣,∣Zi∣≤1091\leq |X|,|Y_i|,|Z_i|\leq 10^9
  • 总共 2×N+12\times N+1 个坐标 X,Yi,ZiX,Y_i,Z_i 互不相同。

样例解释 1

按照以下步骤，高桥君可以以 4040 的最小移动距离到达终点：

  • 从坐标 00 开始。
  • 移动到坐标 33，获得类型 33 的锤子。
  • 移动到坐标 55，获得类型 11 的锤子。
  • 移动到坐标 −2-2，破坏类型 11 的墙。
  • 移动到坐标 −5-5，破坏类型 33 的墙。
  • 移动到坐标 −10-10，获得类型 22 的锤子。
  • 移动到坐标 88，破坏类型 22 的墙。
  • 移动到坐标 1010，到达终点。

样例解释 2

有时不需要获得任何锤子或破坏任何墙就能到达终点。

样例解释 3

高桥君无法获得类型 11 的锤子，因此也无法到达终点。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页