题目思路:模拟 + multiset

cpp代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
#define int long long 

题目内容

有一条笔直的生产线，机器按照位置编号排列（编号为整数）。一台维修机器人初始位于位置 $k$。它沿着生产线匀速移动，每移动一个单位距离需要花费 $m$ 秒。维修操作本身不消耗时间。

在 $0$ 时刻之后，会陆续收到 $n$ 个维修请求。每个请求包含目标位置 $p_i$ 和到达时间 $t_i$，表示在 $t_i$ 秒时，位置 $p_i$ 的机器需要维修。

机器人按照以下规则依次处理所有请求：

• 每当完成一次维修（或初始时刻）时，检查当前时刻及之前已经到达的所有尚未处理的请求。
• 从这些请求中选择一个目标位置 $p$，使得 $|p - ext{当前位置}|$ 最小（即距离最近）。
• 如果存在多个满足条件的请求，则选择位置编号 $p$ 最小的那个。
• 机器人立即移动到该位置，移动距离为 $|p - ext{当前位置}|$，移动耗时等于距离乘以 $m$。到达后立即完成维修（不额外耗时）。
• 如果在某个时刻没有尚未处理的请求，机器人原地等待，直到下一个请求到来的时刻，再将其加入候选集合并继续选择。

你的任务是计算从 $0$ 时刻开始，直到所有请求处理完毕，机器人总共移动的距离（不是时间）。

约束条件：

• 请求次数 $n$ 满足 $1 \le n \le 10^5$。
• 所有位置 $k$、$p_i$ 以及到达时间 $t_i$ 均为正整数，且不超过 $10^9$。
• 单位距离耗时 $m$ 满足 $1 \le m \le 100$。

输入描述

第一行包含三个整数 $n, m, k$，分别表示请求次数、单位距离耗时和机器人初始位置。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示每个请求的目标位置。 第三行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$，表示每个请求的到达时间。请求按输入顺序一一对应，且到达时间不一定有序。

输出描述

输出一个整数，表示机器人总共移动的距离。

样例1

输入

3 2 5
10 2 8
2 5 3

输出

13

说明

初始位置 $k=5$，移动每单位耗时 $m=2$ 秒。 请求按到达时间排序为 $(t=2,p=10)$、$(t=3,p=8)$、$(t=5,p=2)$。

$t=0$ 时无请求，等待至 $t=2$，加入 $p=10$。当前位于 5，距离 $|10-5|=5$，移动 5 格，耗时 $5 imes2=10$ 秒，时间变为 12，位置变为 10，累计移动 5。

$t=12$ 时，检查 $t\le12$ 的请求 $(t=3,p=8)$ 与 $(t=5,p=2)$ 均已到达，候选集合为 $\{8,2\}$。当前位置 10，最近的是 8（距离 2）。移动 2，耗时 $2 imes2=4$ 秒，时间 16，位置 8，累计移动 7。

$t=16$ 时，剩余请求 $\{2\}$，距离 $|2-8|=6$，移动 6，累计移动 13。所有请求处理完毕，总移动距离为 13。

样例2

输入

4 2 10
20 5 25 15
2 4 4 10

输出

45

说明

初始位置 $k=10$，$m=2$。请求排序为 $(t=2,p=20)$、$(t=4,p=5)$、$(t=4,p=25)$、$(t=10,p=15)$。

$t=0$ 等待至 $t=2$，加入 $p=20$。移动距离 $|20-10|=10$，耗时 $10 imes2=20$ 秒，时间变为 22，位置 20，累计移动 10。

$t=22$ 时，$t=4$ 的两个请求和 $t=10$ 的请求均已到达，候选 $\{5,25,15\}$。当前位置 20，计算到每个候选的距离：$|20-5|=15$，$|20-25|=5$，$|20-15|=5$。距离最小的有 25 和 15（均为 5），按规则选位置更小的 15。移动 5，耗时 10 秒，时间 32，位置 15，累计 15。

$t=32$ 时，候选 $\{5,25\}$，距离分别为 10 和 10，选更小的 5。移动 10，耗时 20 秒，时间 52，位置 5，累计 25。

$t=52$ 时，候选 $\{25\}$，移动 20，累计 45。总移动距离为 45。

样例3

输入

1 1 100
1
10

输出

99

说明

只有一个请求 $p=1$，到达时间 $t=10$，初始位置 $k=100$，$m=1$。

$t=0$ 至 $t=10$ 原地等待，$t=10$ 时请求到达，直接移动 $|1-100|=99$ 距离，总移动距离为 99。

样例4

输入

5 3 5
7 3 10 6 4
10 20 10 5 30

输出

13

说明

初始位置 $k=5$，$m=3$。请求排序为 $(t=5,p=6)$、$(t=10,p=7)$、$(t=10,p=10)$、$(t=20,p=3)$、$(t=30,p=4)$。

$t=0$ 等待至 $t=5$，加入 $p=6$。移动 $|6-5|=1$，耗时 $1 imes3=3$ 秒，时间 8，位置 6，累计 1。

$t=8$ 无新请求，等待至 $t=10$，加入 $p=7$。移动 $|7-6|=1$，耗时 3 秒，时间 13，位置 7，累计 2。

$t=13$ 时，另一个 $t=10$ 的请求 $p=10$ 已到达，加入 $10$。移动 $|10-7|=3$，耗时 9 秒，时间 22，位置 10，累计 5。

$t=22$ 时，$t=20$ 的请求 $p=3$ 已到达。移动 $|3-10|=7$，耗时 21 秒，时间 43，位置 3，累计 12。

$t=43$ 时，$t=30$ 的请求 $p=4$ 已到达。移动 $|4-3|=1$，耗时 3 秒，时间 46，位置 4，累计 13。所有请求处理完毕，总移动距离为 13。