2021上海市小学生人工智能算法设计活动 问题 F: 电梯

作者： 作者的头像   洛白さん ,  2021-12-18 12:37:54 ,  所有人可见 ,  阅读 634

3


3

问题 F: 电梯

输入文件: 标准输入 输出文件: 标准输出
时间限制: 1 Sec 内存限制: 256 MB

题目描述

双十一之后照例是快递送包裹的高峰，小 L 住的公寓楼只有一个电梯，所以异常忙碌。
电梯受中控程序的管理，按照一定的规则运行：
1、公寓楼一共有N楼，电梯开始时停在一楼。所有快递员都是从一楼抵达，送货到某一个楼层，等待一定时间，然后返回到一楼后离开。
2、电梯每次从一楼往上移动，直到送到或接到最高楼层的快递员，然后掉头往下直到一楼。途径楼层时，抵达相应楼层的快递员会下电梯，等待电梯返回一楼的快递员会上电梯。
3、电梯在一楼时，如果没有任何快递员抵达或者准备离开，那么电梯将会继续停在一楼。
4、电梯每移动一楼的时间1秒，快递员上下电梯的时间、电梯到达最高层后掉头需要的时间忽略不计。
5、在电梯往上移动的过程中，在送走或接到最高楼层的快递员之前或同时，如果有快递员要从更高楼层坐电梯离开，那么电梯将会继续往上移动去接这个快递员。
6、在电梯往下移动的过程中，如果快递员准备离开时电梯已经低于他的楼层，那么电梯不会返回，快递员必须等下一趟电梯。
小 L 已经知道每个快递员抵达的时间、要去的楼层以及等待的时间，请你计算一下每个快递员离开的时间。

输入

第一行两个整数N和M，表示公寓一共有N楼，一共有M个快递员。
后续M行，每行三个整数A,B,C，A表示一个快递员到达时间（相对于当天零点的秒数），B表示快递员要去的楼层，C表示快递员等待的秒数。按照A从小到大的次序给出。

输出

输出M行，第i行一个整数表示第i个快递员离开公寓的时间（相对于当天零点的秒数）。

样例输入 #1

10 4
32400 5 1
32402 2 1
32425 10 20
32430 2 1

样例输出 #1

32416
32416
32472
32447

样例说明 #1

一共4个快递员，抵达时间依次为：09:00:00、09:00:02、09:00:25、09:00:30。
一号快递抵达后，电梯送到5楼，然后返回1层去接二号快递员，送到2楼后继续往上到5楼接一号快递员，往下时带上在2楼等待的二号快递员。两个快递员同时在 09:00:16 离开。
三号快递员抵达后，电梯送到10楼，然后返回1层去接四号快递员，送到2楼后返回1楼，再回到2楼去接四号快递员，返回1楼后四号快递员于 09:00:47 离开。电梯等待到 09:00:54，上10楼去接三号快递员，并于 09:01:12 返回1楼，三号快递员离开。

数据范围

1 ≤ N ≤ 100，1 ≤ M ≤ 100
32400 ≤ A ≤ 36000，1 ≤ B ≤ N

谢谢浏览！

3 评论

用户头像
Mm5e59   2023-12-09 18:06         踩      回复

@Tianxn大佬，给个正解呗

用户头像
Tianxn   2023-12-14 11:26         踩      回复 
#include<bits/stdc++.h>
using namespace std;

struct person {
    int idx, t;
    bool operator < (const person& p) const {
        return t>p.t;
    }
};

priority_queue<person> storey[105];
priority_queue<person> pq;

int n, m, a[105], b[105], c[105], ans[105];
int idx = 1, t = a[1];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("data.in", "r", stdin);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i] >> b[i] >> c[i];
        if (b[i]==1) ans[i] = a[i]+c[i];
    }

    auto upstairs = [&] (int goal, int& top) {
        int now = 1;
        while (now < goal) {
            now++, t++;
            while (!pq.empty() && pq.top().t<=t) {
                goal = max(goal, b[pq.top().idx]);
                pq.pop();
            }
        }
        top = now;
    };

    auto downstairs = [&] (int now, vector<person>& tmp) {
        while (now > 1) {
            while (storey[now].size() && storey[now].top().t <= t) {
                tmp.push_back(storey[now].top());
                storey[now].pop();
            }
            t++, now--;
        }
    };

    auto update = [&] (vector<person>& tmp) {
        for (auto& x : tmp) {
            ans[x.idx] = t;
        }
    };

    while (idx <= m) {
        // 第一层没人来 看楼上是否有人按下电梯
        if (t<a[idx] && !pq.empty() && pq.top().t<=t) {
            int f = pq.top().idx;
            pq.pop();
            int top = 0;
            vector<person> tmp;
            upstairs(b[f], top);
            downstairs(top, tmp);
            update(tmp);
            continue;
        }

        // 第一层有人来了 需要考虑同时多人上楼的情况
        if (t<a[idx]) t = a[idx];
        int goal = 1;
        while (idx<=m && a[idx]<=t) {
            person p = {idx, t+b[idx]-1+c[idx]};
            pq.push(p);
            storey[b[idx]].push(p);
            if (b[idx]>goal) goal=b[idx];
            idx++;
        }
        int top = 0;
        vector<person> tmp;
        upstairs(goal, top);
        downstairs(top, tmp);
        update(tmp);
    }

    // 楼上还有人
    while (!pq.empty()) {
        person f = pq.top();
        pq.pop();
        t = max(t, f.t);
        if (ans[f.idx]) continue;
        int top = 0;
        vector<person> tmp;
        upstairs(b[f.idx], top);
        downstairs(top, tmp);
        update(tmp);
    }

    for (int i = 1; i <= m; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}
用户头像
Gracezhuzhu   2022-11-15 21:03         踩      回复

$正解不给的吗。。。$