#P1269. 2023.04.29-春招-第四题-SSTF算法
2023.04.29-春招-第四题-SSTF算法
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
塔子哥是一名磁盘维修师,他的工作是检查和修复损坏的磁盘。为了提高工作效率,他使用了一种最短服务时间优先(SSTF)算法来安排他的磁盘读取请求。每当他收到一个需要读取某个磁道上的数据的请求,他就把它加入到一个队列中。然后,他按照SSTF算法的规则,选择一个最适合当前磁头位置的请求来执行。这样,他可以减少磁头移动的距离,节省时间和能源。
现在,塔子哥想要知道,在一段时间内,他的磁头总共移动了多少个磁道。
给定 0 时刻的磁头位置和速度,以及随后的一系列请求,请你帮助塔子哥计算出这个数目。
SSTF算法的规则如下:每执行完一次磁盘读取后(读取时间忽略),检查当前时刻及其之前到达的所有请求,服务距离当前磁道最近的请求。当有多个磁头距离当前值较近时,服务磁道号较小的请求。若当前时刻及其之前到达的所有请求都已经处理,磁头停留不动,等待下一个请求到来。
输入第一行三个正整数 n,m,k ,表示磁盘请求次数为 n ,磁头每移动 1 个磁道花费的时间为 m ,磁头初始所在磁道号是 k 。
输入第二行 n 个正整数 ai ,表示第 i 次请求的磁道号。
输入第三行 n 个正整数 ti ,表示第 i 次请求的到达时间,不保证该序列递增。
对于所有的数据: $1\le n\le 10^5,1\le a_i,t_i\le 10^9 , 1 \leq m \leq 100$ 。
输出为一个整数,表示磁头移动的总磁道数。
输入
5 1 5
3 4 1 8 5
10 4 9 7 8
输出
12
样例解释
0时刻进入等待状态至4时刻 当前请求队列为(数字代表磁道号):{ 4 }
4 时刻 磁头从5号磁道 移动到 4号磁道 ,5时刻到达, 当前移动长度为1
5时刻进入等待状态至7时刻 当前请求队列为(数字代表磁道号):{ 8 }
7 时刻 磁头从4号磁道 移动到 8号磁道 ,11时刻到达, 当前移动长度为5 当前请求队列为(数字代表磁道号):{ 1 3 5 }
11 时刻 磁头从8号磁道 移动到 5号磁道 ,14时刻到达, 当前移动长度为8 当前请求队列为(数字代表磁道号):{ 1 3 }
14 时刻 磁头从5号磁道 移动到 3号磁道 ,16时刻到达, 当前移动长度为10 当前请求队列为(数字代表磁道号):{ 1 }
16 时刻 磁头从3号磁道 移动到 1号磁道 ,18时刻到达, 当前移动长度为12
总移动长度为12
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.