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

CFCF2193F.Pizza Delivery

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

外卖员 YF 获得了最佳披萨外卖员 GR 的称号。但经理不喜欢他，于是给了他一个非常困难的任务。经理给了他 nn 个房子的坐标 (xi,yi)(x_i, y_i)，他需要将披萨送到这些房子。他将按照以下方式配送披萨：

  • GR 披萨在点 (Ax,Ay)(Ax, Ay) 被制作，YF 从这个点开始配送。
  • 他可以从 (x,y)(x, y) 移动到 (x+1,y)(x+1, y)、(x,y+1)(x, y+1) 或 (x,y−1)(x, y-1) 这三个点中的任意一个。
  • 在送完所有披萨后，他需要返回家中，即回到 (Bx,By)(Bx, By)。

每次移动恰好需要一秒钟，交付披萨不用花时间（00 秒）。经理希望配送用时越短越好。你需要计算完成所有 GR 披萨配送的最短时间。保证一定可以完成所有披萨的配送。

输入格式

每个测试包含若干组测试数据。第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4）——测试数据的组数。接下来是每组测试数据。

每组测试的第一行包含五个整数 nn、AxAx、AyAy、BxBx、ByBy（1≤n≤2⋅1051 \le n \le 2 \cdot 10^5，1≤Ax,Ay,Bx,By≤1091 \le Ax, Ay, Bx, By \le 10^9），表示需要配送的房子数量及起点和终点的坐标。

第二行包含 nn 个整数 x1,x2,…,xnx_1, x_2, \dots, x_n（Ax<xi<BxAx < x_i < Bx）。

第三行包含 nn 个整数 y1,y2,…,yny_1, y_2, \dots, y_n（1≤yi≤1091 \le y_i \le 10^9）。

保证所有组测试中 nn 的总和不超过 2⋅1052 \cdot 10^5。

输出格式

对于每组测试数据，输出一个整数，占一行，表示完成披萨配送的最短时间。

输入输出样例

  • 输入#1

    4
1 2 3 5 2
4
4
3 1 3 5 2
3 4 3
5 4 1
6 1 2 7 3
5 2 3 5 5 3
6 4 3 1 4 1
5 6 9 8 6
7 7 7 7 7
3 1 8 8 3

    输出#1

    6
13
19
15

说明/提示

以第二组测试数据为例：

  • 从 (Ax,Ay)(Ax, Ay) 移动到 (x3,y3)(x_3, y_3) 需 44 秒。
  • 从 (x3,y3)(x_3, y_3) 移动到 (x1,y1)(x_1, y_1) 需 44 秒。
  • 从 (x1,y1)(x_1, y_1) 移动到 (x2,y2)(x_2, y_2) 需 22 秒。
  • 从 (x2,y2)(x_2, y_2) 移动到 (Bx,By)(Bx, By) 需 33 秒。

总耗时 4+4+2+3=134+4+2+3=13 秒。可以证明无法再更快完成配送。

首页