题目思路:模拟 + multiset

cpp代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
#define int long long 
pair<int,int> task_seq[maxn];
signed main()
{
    int n , m , k;
    cin >> n >> m >> k;
    for (int i = 1 ; i <= n ; i++)
        cin >> task_seq[i].second;
    for (int i = 1 ; i <= n ; i++)
        cin >> task_seq[i].first;
    sort(task_seq + 1 , task_seq + 1 + n);

    multiset<int> task_que;
    int step = 0;
    int now_time = 0;
    int now_pos = k;
    int now_it = 1;
    int rest_task = n;
    do{
        // 1.add new
        bool wait = true;
        while (now_it <= n && task_seq[now_it].first <= now_time){
            //cout << task_seq[now_it].first << " " << task_seq[now_it].second << " into que" << endl;
            task_que.insert(task_seq[now_it++].second);
            wait = false;
        }
        // wait
        if (wait && task_que.size() == 0){
            now_time = task_seq[now_it].first;
            task_que.insert(task_seq[now_it++].second);
        }
        // get nearest
        int target;
        int min_dist = 1e9;
        auto ri = task_que.lower_bound(now_pos);
        auto rm = ri;
        if (ri != task_que.end()) {
            int ri_dist = abs(*ri - now_pos);
            min_dist = ri_dist;
            target = *ri;
        }
        if (ri != task_que.begin()){
            auto le = ri;
            le--;
            int le_dist = abs(*le - now_pos);
            if (le_dist <= min_dist) {
                target = *le;
                min_dist = le_dist;
                rm = le;
            }
        }
        task_que.erase(rm);
        // 3.move
        rest_task--;
        int dist = abs(now_pos - target);
        step += dist;
        now_time += dist * m;
        now_pos = target;
    }while (rest_task > 0);
    cout << step << endl;
    return 0;
}

/*
2 1 1
1 4
1 123
*/

题目内容

小美是一名磁盘维修师，他的工作是检查和修复损坏的磁盘。为了提高工作效率，他使用了一种最短服务时间优先(SSTF)算法来安排他的磁盘读取请求。每当他收到一个需要读取某个磁道上的数据的请求，他就把它加入到一个队列中。然后，他按照SSTF算法的规则，选择一个最适合当前磁头位置的请求来执行。这样，他可以减少磁头移动的距离，节省时间和能源。

现在，小美想要知道，在一段时间内，他的磁头总共移动了多少个磁道。

给定 $0$ 时刻的磁头位置和速度，以及随后的一系列请求，请你帮助小美计算出这个数目。

SSTF算法的规则如下：每执行完一次磁盘读取后(读取时间忽略)，检查当前时刻及其之前到达的所有请求，服务距离当前磁道最近的请求。当有多个磁头距离当前值较近时，服务磁道号较小的请求。若当前时刻及其之前到达的所有请求都已经处理，磁头停留不动，等待下一个请求到来。

输入描述

输入第一行三个正整数 $n,m,k$ ，表示磁盘请求次数为 $n$ ，磁头每移动 $1$ 个磁道花费的时间为 $m$ ，磁头初始所在磁道号是 $k$ 。

输入第二行 $n$ 个正整数 $a_i$ ，表示第 $i$ 次请求的磁道号。

输入第三行 $n$ 个正整数 $t_i$ ，表示第 $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